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.
1from typing import List
2
3class Solution:
4 def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
5 n = len(books)
6 dp = [0] + [float('inf')] * n
7 for i in range(1, n + 1):
8 width = height = 0
9 for j in range(i, 0, -1):
10 width += books[j - 1][0]
11 if width > shelfWidth: break
12 height = max(height, books[j - 1][1])
13 dp[i] = min(dp[i], dp[j - 1] + height)
14 return dp[n]The Python approach makes use of a list to store dp values. For each book, we attempt every possible placement and select the one yielding the least height increase. The process takes into account all combinations up to the shelf width constraint.
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.