Filling Bookcase Shelves

Leetcode Problem:

• Filling Bookcase Shelves

Summary

• The problem is to find the minimum possible height of a bookcase with given shelf width and a list of books, where each book has a thickness and a height.

Approach

• Dynamic programming is used to solve this problem
• The approach is to calculate the minimum possible height for each book and each shelf, and then choose the minimum height at each step.

Complexity

• The time complexity of this solution is O(N^2), where N is the number of books
• This is because there are two nested loops in the solution code.

Explain

• The solution code uses a dynamic programming approach to solve the problem
• It initializes an array dp of size 1001 to store the minimum possible height for each book and each shelf
• Then, it iterates over each book and each shelf, and for each shelf, it calculates the minimum possible height by considering all possible combinations of books on the shelf
• Finally, it returns the minimum possible height for the last book and the last shelf.

Solution Code:

class Solution {
public:
    int dp[1001];
    int minHeightShelves(vector>& books, int shelfWidth) {
        int N = books.size();
        for(int i = 1; i <= N; i++){
            int width = books[i-1][0];
            int height = books[i-1][1];
            dp[i] = dp[i-1] + height;
            for(int j = i -1; j > 0; j--){
                height = max(height, books[j-1][1]);
                width += books[j-1][0];
                if (width > shelfWidth) break;
                dp[i] = min(dp[j-1] + height, dp[i]);
            }
        }
        return dp[N];
    }
};