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.
1public class Solution {
2 public int MinHeightShelves(int[][] books, int shelfWidth) {
3 int n = books.Length;
4 int[] dp = new int[n + 1];
5 Array.Fill(dp, int.MaxValue);
6 dp[0] = 0;
7 for (int i = 1; i <= n; i++) {
8 int width = 0, height = 0;
9 for (int j = i; j > 0; j--) {
10 width += books[j - 1][0];
11 if (width > shelfWidth) break;
12 height = Math.Max(height, books[j - 1][1]);
13 dp[i] = Math.Min(dp[i], dp[j - 1] + height);
14 }
15 }
16 return dp[n];
17 }
18}The C# solution closely follows the same logic employed in the C and Java approaches. It dynamically calculates the minimum height for each configuration of book placements, updating the dp array as it progresses through each "shelf-ending" scenario for book i.
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.