1105. 填充书架

Difficulty

Medium

Tags

动态规划

URL

https://leetcode-cn.com/problems/filling-bookcase-shelves/

Star

❤

附近的家居城促销，你买回了一直心仪的可调节书架，打算把自己的书都整理到新的书架上。

你把要摆放的书 books 都整理好，叠成一摞：从上往下，第 i 本书的厚度为 books[i][0]，高度为 books[i][1]。

按顺序 将这些书摆放到总宽度为 shelf_width 的书架上。

先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelf_width），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。

需要注意的是，在上述过程的每个步骤中，摆放书的顺序与你整理好的顺序相同。例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。

每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。

以这种方式布置书架，返回书架整体可能的最小高度。

示例：


输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4
输出：6
解释：
3 层书架的高度和为 1 + 3 + 2 = 6 。
第 2 本书不必放在第一层书架上。

提示：

1 <= books.length <= 1000

1 <= books[i][0] <= shelf_width <= 1000

1 <= books[i][1] <= 1000

通过次数5,002提交次数9,005

法1 动态规划

思路

换个表达方式：

将给定多个list分组，要求如下：

list顺序不能乱（题目要求了按顺序从上到下摆放）

每组list中每个list首元素之和不能超过一定值（书架限制宽度）

定义每组高度为该组所有list次元素的最大值。然后求使得使得所有组高度之和最小的高度。

在示例中，给定的多个list为[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2] ，限制书架宽度为4.所以采用如下分组方式：


[1,1]
[2,3],[2,3]
[1,1],[1,1],[1,1],[1,2]

最后所得总高度为 1 + 3 + 2 = 6

题目只是多追加了一个应用场景，且用图例的方式解释了书的摆放，起始图上的序号并没有实际意义，只是代表了第几本书，即多个list的序号，而1，2，3这样按照顺序下来也只是按照题目的要求按顺序从上到下摆放。

所以本题实质上就是动态规划第二类基本型：”时间序列“加强版。

那么按照套路定义dp如下：

dp[i] 以下标i本书为结尾的书books[0:i] (左右均闭合)的摆放最低高度。

状态如下：

第i本书所在的这一层可能有多高？取决于上一层的最后一本书在哪里。即 dp[i] 取决于dp[j]， j为上一层（上一组）最后一本书。那么dp[i] = dp[j] + max(books[j+1:i+1]).所以还是寻找最优前驱j

注：此处定义了j为上一层最后一本书，所以有一个bug,那就是当只有两本书时，必定会分为两层存放，即使一层可以放得下！所以定义dp时长度应该为 len(books)+1。第一本书是放在dp下标为1的位置的。即当i=2时，此时对应的书为books[1]。

题解


class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        dp = [float('inf') for i in range(len(books) + 1)]
        dp[0] = 0
        for i in range(1, len(dp)):
            for j in range(i-1, -1, -1):
                # 从后往前查找 j 更高效 
                if sum([book[0] for book in books[j:i]]) > shelfWidth:
                    break
                if max([book[1] for book in books[j:i]]) + dp[j] <= dp[i]:
                    dp[i] = max([book[1] for book in books[j:i]]) + dp[j]
        return dp[-1]

本题，dp数组于书的对应关系容易错乱。在写题目的时候，对于两个for循环套路依旧不变，在索引书的时候切记不要弄乱。当然也可以通过重新定义j,使得j为当前层的第一本书，这样只需要注意一个地方。代码如下：


class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        dp = [float('inf') for i in range(len(books))]
        dp[0] = books[0][1]

        for i in range(1, len(dp)):
            for j in range(i, -1, -1):  # 当前层是可能只有一本书的
                # 当前层宽度
                width = sum([book[0] for book in books[j:i+1]]) 
                if width <= shelfWidth:
                    # 当前层高度
                    height = max([book[1] for book in books[j:i+1]]) 
                    # 前一层高度
                    lastHeight = dp[j-1] if j > 0 else 0
                    # 更新dp[i]
                    dp[i] = min(height + lastHeight, dp[i])
        return dp[-1]

优化：

计算当前层的宽度的时候，不用每次都从 i 到 j 加一遍，可以逐渐累计，

同理，当前层的高度也是不用每次都算一遍，可以逐次取max。

当宽度超过书架的时候，j 就不用往前看了，直接break ，表示当前层已经确定了


class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        dp = [float("inf") for _ in books]
        dp[0] = books[0][1]

        for i in range(1, len(books)):
            # j 是当前层的第一本数
            # w,h 表示当前层的 宽度 和 高度
            w, h = 0, 0
            for j in range(i, -1, -1):
                # 更新 宽度 和高度
                w += books[j][0]
                h = max(h, books[j][1])
                if w <= shelfWidth:
                    if j >= 1:
                        prev_heidth = dp[j-1]
                    else:
                        prev_heidth = 0
                    dp[i] = min(dp[i], prev_heidth + h)
                else:
                    break

        return dp[-1]