Another medium LC problem in which we are asked to arrange the books in a bookshelf with certain width and try to minimize the total height of the books after the arrangement.
To solve the problem, we’re going to use dynamic programming to keep track of the height of each row of books. We’re going to use this information to decide whether we should add more books into that row to skip to the next row instead.
So for every book, we’ll put it into a new row, update the max height for that row, then check all the other previous books and see if we can bring them down to our new row. If we can bring them down, making sure the new width is still below or equal to the shelf width, then we’ll update the row’s max height, but only if we can reduce the row’s height.
Time Complexity: O(n^2)
class Solution {
public int minHeightShelves(int[][] books, int shelf_width) {
// use dynamic programming
// put each book in a new shelve
// then try to bring down 1 book and see if it will fit shelf width
// if it can, then update the max height for that shelf
int n = books.length;
int[] dp = new int[n + 1];
dp[0] = 0;
for(int i=1; i <= n; i++){
int width = books[i-1][0];
int height = books[i-1][1];
// put into a new shelf
dp[i] = dp[i-1] + height;
for(int j = i - 1; j > 0; j--){
width += books[j - 1][0];
if(width > shelf_width) continue;
// yes we can fit this book into the current shelf
// so update the max height
height = Math.max(height, books[j - 1][1]);
// finally update our shelf max height
// only do it if it will eventually lower the height down
dp[i] = Math.min(dp[i], dp[j-1] + height);
}
}
return dp[n];
}
}
Runtime: 2 ms, faster than 16.15% of Java online submissions for Filling Bookcase Shelves.
Memory Usage: 37.7 MB, less than 100.00% of Java online submissions for Filling Bookcase Shelves.