You are given an array books where books[i] = [thicknessi, heighti] indicates the thickness and height of the ith book. You are also given an integer shelfWidth.
We want to place these books in order onto bookcase shelves that have a total width shelfWidth.
We choose some of the books to place on this shelf such that the sum of their thickness is less than or equal to shelfWidth, then build another level of the shelf of the bookcase so that the total height of the bookcase has increased by the maximum height of the books we just put down. We repeat this process until there are no more books to place.
Note that at each step of the above process, the order of the books we place is the same order as the given sequence of books.
5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf.Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.
Example 1:
Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4 Output: 6 Explanation: The sum of the heights of the 3 shelves is 1 + 3 + 2 = 6. Notice that book number 2 does not have to be on the first shelf.
Example 2:
Input: books = [[1,3],[2,4],[3,2]], shelfWidth = 6 Output: 4
Constraints:
1 <= books.length <= 10001 <= thicknessi <= shelfWidth <= 10001 <= heighti <= 1000This approach involves using dynamic programming to decide the optimal cutting of shelves using the given books. Let df[i] be the minimum height for placing the first i books. For each book i, you consider ending a new shelf at book i but try every starting point from j = i to find the best cut. The key here is to use a nested loop to calculate the minimum height iteratively.
This solution uses an integer array df of size booksSize + 1, where each element df[i] represents the minimum height of the bookshelf containing the first i books. Two nested loops check each combination to find the minimum. The outer loop selects to end a shelf with the i-th book, while the inner loop determines the start of that shelf.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where n is the number of books.
Space Complexity: O(n), due to the use of extra space for the dp array.
This strategy uses a recursive backtracking approach augmented with memoization to avoid redundant calculations. By attempting to place books on shelves recursively and caching computed heights, it achieves optimal placement efficiently. This method provides a balance between direct computation and saved results.
The C code recursively tries to place each book on a new shelf or the current shelf. It uses a memoization array dp to store computed minimum heights for the subproblems, avoiding recomputation. This recursion explores every possibility and chooses the arrangement yielding the minimum height incrementally.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), primarily constrained due to state saving over recursion calls
Space Complexity: O(n), requires extra space for memoization.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2), where n is the number of books. |
| Backtracking with Memoization | Time Complexity: O(n^2), primarily constrained due to state saving over recursion calls |
Filling Bookcase Shelves - Leetcode 1105 - Python • NeetCodeIO • 17,606 views views
Watch 9 more video solutions →Practice Filling Bookcase Shelves with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor