Sponsored
Sponsored
This 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.
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.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
8 int n = books.size();
9 vector<int> dp(n + 1, INT_MAX);
10 dp[0] = 0;
11 for (int i = 1; i <= n; i++) {
12 int width = 0, height = 0;
13 for (int j = i; j > 0; j--) {
14 width += books[j - 1][0];
15 if (width > shelfWidth) break;
16 height = max(height, books[j - 1][1]);
17 dp[i] = min(dp[i], dp[j - 1] + height);
18 }
19 }
20 return dp[n];
21 }
22};Similar to the C solution, but here we use a vector to store dp values. The solution checks each combination of placements for books on a shelf and picks the combination with the minimum height.
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.
Time Complexity: O(n^2), primarily constrained due to state saving over recursion calls
Space Complexity: O(n), requires extra space for memoization.
1
In the Java solution, a recursive helper function helper decides each potential shelf/book arrangement, storing previously computed results to efficiently skip unnecessary recalculations. This dynamic evaluation supports reaching the minimum height scenario over many recursive steps.