# 1105. Filling Bookcase Shelves
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/filling-bookcase-shelves/
## 思路
原型是[1043. Partition Array for Maximum Sum](https://hackmd.io/sSjKhGdcQrmWNvAvq0s6bw)

我们遍历```i```之前的index ```j``` 把他们当作这一层的第一本书
那么```i```所在的这一层的width就是从```j```到```i```的所有书的width和

只要width没有超过shelfWidth ```dp[i]```就可以等于```dp[j-1]+maxHeight```

注意初始值```dp[0]```要设成```0```并且要在books的开头加上```[0,0]```这本书 不然第一本书永远不能和别的书在同一层(会一直被当成上一层的最后一本)
## Code

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        
        List<int[]> bookList = new ArrayList<>();
        for(int i=0; i<=n; i++){
            if(i==0) bookList.add(new int[]{0,0});
            else{
                bookList.add(books[i-1]);
            }
        }
        dp[0] = 0;
        
        for(int i=1; i<=n; i++){
            int currWidth = bookList.get(i)[0];
            int maxHeight = bookList.get(i)[1];
            dp[i] = dp[i-1]+maxHeight;
            for(int j=i-1; j>=1; j--){
                maxHeight = Math.max(maxHeight, bookList.get(j)[1]);
                currWidth += bookList.get(j)[0];
                if(currWidth<=shelfWidth){
                    dp[i] = Math.min(dp[i], dp[j-1]+maxHeight);
                }
                else break;
            }
        }
        return dp[n];
    }
}