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 <stdio.h>
2#include <limits.h>
3
4int minHeightShelves(int books[][2], int booksSize, int* booksColSize, int shelfWidth) {
5 int dp[booksSize + 1];
6 dp[0] = 0;
7 for (int i = 1; i <= booksSize; i++) {
8 int width = 0, height = 0;
9 dp[i] = INT_MAX;
10 for (int j = i; j > 0; j--) {
11 width += books[j - 1][0];
12 if (width > shelfWidth) break;
13 height = height > books[j - 1][1] ? height : books[j - 1][1];
14 if (dp[j-1] + height < dp[i]) dp[i] = dp[j-1] + height;
15 }
16 }
17 return dp[booksSize];
18}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.
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.