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
public class Solution {
public int MinHeightShelves(int[][] books, int shelfWidth) {
int[] dp = new int[books.Length];
Array.Fill(dp, -1);
return MinHeight(books, shelfWidth, 0, dp);
}
private int MinHeight(int[][] books, int shelfWidth, int pos, int[] dp) {
if (pos == books.Length) return 0;
if (dp[pos] != -1) return dp[pos];
int width = 0, height = 0, minHeight = int.MaxValue;
for (int i = pos; i < books.Length; i++) {
width += books[i][0];
if (width > shelfWidth) break;
height = Math.Max(height, books[i][1]);
minHeight = Math.Min(minHeight, height + MinHeight(books, shelfWidth, i + 1, dp));
}
dp[pos] = minHeight;
return minHeight;
}
}The C# solution employs a similar recursive strategy backed by memoization. The MinHeight function recursively evaluates further book placement, using an array dp to reduce repeated calculations at each positional decision.