1105. Filling Bookcase Shelves

Problem

Filling Bookcase Shelves

Approach

Given DP[i] is the minimum height for the previous i books, which is books[:i + 1]. So, we can get DP[i] from DP[i - 1]. More importantly, as for books[i] we have two choices that the first one is to put the book on a new level and the another is to put some books next to i-th book together, maybe books[j], books[j + 1], ... , books[i]. Consider the second choice, because i-th book is the last one, so we must try our best to put more books in the same level to decrease the last answer.

Code

class Solution {
    public int minHeightShelves(int[][] books, int shelf_width) {
        int n = books.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for(int i = 1; i < dp.length; i ++){
            int h = books[i - 1][1];
            dp[i] = dp[i - 1] + h;
            int cw = books[i - 1][0];
            int hmax = books[i - 1][1];
            for(int j = i - 2; j >= 0; j --){
                if(cw + books[j][0] > shelf_width){
                    break;
                }
                else{
                    cw += books[j][0];
                    hmax = Math.max(hmax, books[j][1]);
                    dp[i] = Math.min(dp[i], dp[j] + hmax);
                }
            }
        }
        return dp[n];
    }
}