1105. 填充书架

ITCharge大约 3 分钟

---

1105. 填充书架

标签：数组、动态规划
难度：中等

题目链接

1105. 填充书架 - 力扣

题目大意

描述：给定一个数组 $books$ ，其中 $books[i] = [thickness_i, height_i]$ 表示第 $i$ 本书的厚度和高度。还有一个书架宽度 $shelfWidth$ 。

你需要按顺序（不能打乱书的顺序）把这些书摆放到书架上。摆放规则是：

先放几本书在第一层，它们的厚度之和不能超过 $shelfWidth$ 。
然后建第二层，继续放，依此类推。
每一层的高度由该层中最高的那本书决定。
书架的总高度 = 所有层的高度之和。

要求：计算书架可能的最小总高度。

说明：

$1 \le books.length \le 10^{3}$ 。
$1 \le thickness_i \le shelfWidth \le 10^{3}$ 。
$1 \le height_i \le 10^{3}$ 。

示例：

输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
输出：6
解释：3 层书架的高度和为 1 + 3 + 2 = 6。

解题思路

思路 1：动态规划

这道题可以想象成「切香肠」——把一长串书按顺序切成若干段（每一段就是一层的书），每段的总厚度不能超过书架宽度，每段的高度由该段中最高的书决定。我们要找一种切法，让各段高度之和最小。

动态规划（可以把大问题拆成小问题，先解决简单的子问题，再一步步推到复杂情况）的思路是这样的：

定义状态。 设 $dp[i]$ 表示「放好前 $i$ 本书所需的最小总高度」。
从后往前推。 当我们处理第 $i$ 本书时，考虑它所在的这一层从哪里开始：
- 也许第 $i$ 本书单独占一层（从 $i$ 到 $i$ ）。
- 也许它和前面的第 $i-1$ 本书挤在同一层。
- 也许再往前面加书……直到厚度超了为止。
状态转移。 用 $j$ 表示当前层的第一本书的位置（从 $j$ 到 $i$ 是同一层），那么：
- 从 $j$ 到 $i$ 的总厚度不能超过书架宽度。
- 这一层的高度 = 从 $j$ 到 $i$ 的所有书的最大高度。
- 总高度 = 前 $j-1$ 本书的最小高度（ $dp[j-1]$ ）+ 本层高度。
- 取所有可能的 $j$ 中，总高度最小的那个。

用人话讲就是：尝试把最后几本书放在同一层，每一种分法都算一下总高度，选最小的。

步骤拆解：

初始化 $dp[0] = 0$ （0 本书高度为 0），其他 $dp[i]$ 设为无穷大。
从第 1 本书遍历到第 $n$ 本书（ $i$ 从 1 到 $n$ ）：
- 设 $width = 0$ ， $height = 0$ 。
- 从第 $i$ $i$ 本书往前看（ $j$ $j$ 从 $i$ $i$ 到 1）：
  - 把第 $j$ 本书加到当前层的厚度里，如果超宽就停止。
  - 更新当前层的最大高度。
  - 计算 $dp[j-1] + height$ ，更新 $dp[i]$ 。
返回 $dp[n]$ 。

思路 1：代码

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        n = len(books)
        # dp[i] 表示放好前 i 本书所需的最小书架高度
        dp = [float('inf')] * (n + 1)
        dp[0] = 0  # 没有书时高度为 0
        
        for i in range(1, n + 1):
            width = 0   # 当前层的总厚度
            height = 0  # 当前层的最大高度
            
            # 从第 i 本书往前，尝试把它们放在同一层
            for j in range(i, 0, -1):
                # 把第 j 本书加进当前层
                width += books[j - 1][0]
                # 如果超宽了，后面的 j 只会更宽（因为书是往前的），直接停下
                if width > shelfWidth:
                    break
                # 更新当前层的最高高度
                height = max(height, books[j - 1][1])
                # 前 j-1 本书的高度 + 当前层高度，取最小值
                dp[i] = min(dp[i], dp[j - 1] + height)
        
        return dp[n]

思路 1：复杂度分析

时间复杂度： $O(n^2)$ 。用人话说就是：每本书都要往前检查最多 $n$ 本书，最坏情况下要算 $n^2$ 次。好在 $n$ 最多 1000，可以接受。
空间复杂度： $O(n)$ 。需要一个长度为 $n+1$ 的数组来记录状态。