1105. 填充书架 - Java 动态规划

原题地址：https://leetcode.cn/problems/filling-bookcase-shelves/

题解

设dp[i]为将前i本书放入书架的最小高度，由于只能按顺序往里填充，我们可以考虑如下几种情况：

• 第i本书单独占一个书架，高度等于前i-1本书的最小高度加上第i本书自己的高度
  • 这种情况下dp[i]=dp[i-1]+height[i]
• 将最后一层的第i-1本书拿出来，和第i本书共两本书组成一层书架，此时这层书架等于这两本书高度的最大值
  • 这种情况下dp[i]=dp[i-2]+max(height[i],height[i-1])
• 以此类推，将从后数第j本书拿出来，和第i本书共j+1本书组成一层书架，此时这层书架等于这j+1本书高度的最大值
  • 这种情况下dp[i]=dp[i-j-1]+max(height[i],…,height[i-j])

以此类推，一直到这j+1本书的总宽度>书架宽度为止，就是这层书架能够满足的所有情况，我们对所有情况取最小值就是书架的最小高度，有：

要注意的是，第一本书的高度height[1]并不对应books[1]而是books[0]，所以对于任意i有

边界条件：

初始化dp[0]=0，即放入0本书时的高度为0即可，此时有dp[1]=dp[0]+height[1]=height[1]

时间复杂度：O(N^2)

空间复杂度：O(N)

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int[] dp=new int[books.length+1];
        dp[0]=0;

        int widthSum,maxHeight,minHeight,totalHeight;
        for(int i=1;i<dp.length;i++){
            widthSum=0;
            minHeight=Integer.MAX_VALUE;
            maxHeight=Integer.MIN_VALUE;
            for (int j=0;j<i;j++){
                widthSum+=books[i-j-1][0];
                if(widthSum>shelfWidth)break;

                maxHeight=Math.max(maxHeight,books[i-j-1][1]);
                totalHeight=dp[i-j-1]+maxHeight;
                minHeight=Math.min(minHeight,totalHeight);
            }
            dp[i]=minHeight;
        }
        return dp[dp.length-1];
    }
}