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#include <vector>
#include <limits>
using namespace std;
class Solution {
int dfs(vector<vector<int>> & books, int shelfWidth, int pos, vector<int> & dp) {
if (pos == books.size()) return 0;
if (dp[pos] != -1) return dp[pos];
int width = 0, height = 0, minHeight = INT_MAX;
for (int i = pos; i < books.size(); i++) {
width += books[i][0];
if (width > shelfWidth) break;
height = max(height, books[i][1]);
minHeight = min(minHeight, height + dfs(books, shelfWidth, i + 1, dp));
}
dp[pos] = minHeight;
return minHeight;
}
public:
int minHeightShelves(vector<math>> books, int shelfWidth) {
vector<int> dp(books.size(), -1);
return dfs(books, shelfWidth, 0, dp);
}
};The C++ version uses a recursive helper function dfs to try placing books starting from the current position, memoizing results to avoid recalculating overlaps. The function optimally decides the next step by considering when placing on a new shelf might be more beneficial than continuing on the current one.