LeetCode 1105. Filling Bookcase Shelves

Problem

LeetCode 1105. Filling Bookcase Shelves

1. 题目简述

给出一堆书和一个书架，每本书有宽和高，书架有宽度w，我们需要按照给定的顺序排列书籍，求出书架最少需要多高才能放下所有的书籍（建议去看leetcode原本题目，这里表述比较简略）。例如：

Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4

Output: 6

Explanation:
The sum of the heights of the 3 shelves are 1 + 3 + 2 = 6.
Notice that book number 2 does not have to be on the first shelf.

2. 算法思路

参考资料：

1. 花花酱的解析

dynamic programming

这是一道十分典型的动态规划问题，没遇到很难想出来。

这里看似是一个二维的问题，实际上是一维。限制条件就是书架的宽度，这里就先不放图片了，在上面花花酱的视频里面有解释。对于任意第i本书，它有两种可能性，一种是从它自身开始重新加一层，另一种方式就是和前面的一些书一起构成一层。但是具体怎么样才算是最优解我们并不清楚，也没有判断的方法。

Greedy肯定是不可用的，因为即使我们找到了当前的最优解，也不确定它是否是全局最优解的一部分。因此我们需要遍历所有可能的书架上书的排列情况。

我们假设dp[i]是对于前i本书，最小的高度。

那么从第i本书向前搜索x本书，x本书的宽度不超过书架宽度(0<= x < i)，height(i, j)表示从第i本书到第j本书最高高度。那么有：

$$dp[i] = min(dp[i - x] + height(i - x, i)， dp[i]) (x本书的宽度要小于书架宽度)$$

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

        // dp[i]表示前i个元素组成的书架的最小高度，对于所有的j在0到i-1之间的书，我们从后向前找x本书，使得x本书的宽度不会超过书架的width，dp[i] = min(dp[i], dp[j] + height) j在0到i-1之间。

        Arrays.fill(dp, 1000000);
        // 初始化dp[0]和dp[1]
        dp[1] = books[0][1];
        dp[0] = 0;
        for (int i = 2; i <= n; i++) {
            int width = 0, height = -1;
            for (int j = i; j > 0; j--) {
                width += books[j - 1][0];
                height = Math.max(height, books[j - 1][1]);
                if (width <= shelf_width) {
                    dp[i] = Math.min(dp[j - 1] + height, dp[i]);
                } else {
                    break;
                }
            }
        }

        return dp[n];
    }
}