LeetCode 题解工作台
填充书架
给定一个数组 books ，其中 books[i] = [thickness i , height i ] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。 按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。 先选几本书放在书架上（它们的厚度之和小于等于书架的…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义 表示前 本书摆放的最小高度，初始时 $f[0] = 0$，答案为 。 考虑 ，最后一本书为 $books[i - 1]$，其厚度为 ，高度为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给定一个数组 books ，其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。
按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。
先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。
需要注意的是，在上述过程的每个步骤中，摆放书的顺序与给定图书数组 books 顺序相同。
- 例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。
每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。
以这种方式布置书架，返回书架整体可能的最小高度。
示例 1：
输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4 输出：6 解释： 3 层书架的高度和为 1 + 3 + 2 = 6 。 第 2 本书不必放在第一层书架上。
示例 2:
输入: books = [[1,3],[2,4],[3,2]], shelfWidth = 6 输出: 4
提示：
1 <= books.length <= 10001 <= thicknessi <= shelfWidth <= 10001 <= heighti <= 1000
解题思路
方法一：动态规划
我们定义 表示前 本书摆放的最小高度，初始时 ，答案为 。
考虑 ，最后一本书为 ，其厚度为 ，高度为 。
- 如果这本书单独摆放在新的一层，那么有 ；
- 如果这本书可以与前面的最后几本书摆放在同一层，我们从后往前枚举同一层的第一本书 ，其中 ，将书的厚度累积到 ，如果 ，说明此时的 已经无法与 摆放在同一层，停止枚举；否则我们更新当前层的最大高度 ，那么此时有 。
最终的答案即为 。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
n = len(books)
f = [0] * (n + 1)
for i, (w, h) in enumerate(books, 1):
f[i] = f[i - 1] + h
for j in range(i - 1, 0, -1):
w += books[j - 1][0]
if w > shelfWidth:
break
h = max(h, books[j - 1][1])
f[i] = min(f[i], f[j - 1] + h)
return f[n]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N \cdot W) because for each book we may examine up to W width for possible shelf placements. Space complexity is O(N) for storing dp values for each starting index. |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Check if you can place multiple consecutive books per shelf without exceeding shelfWidth.
- question_mark
Ask about defining the subproblem in terms of remaining books to apply state transition DP.
- question_mark
Consider memoization to optimize repeated calculations for overlapping subproblems.
常见陷阱
外企场景- error
Not handling the shelf height correctly by always taking the maximum book height per shelf.
- error
Failing to maintain the order of books, which is required for this problem's DP formulation.
- error
Ignoring memoization, leading to excessive recursive calls and timeouts for larger inputs.
进阶变体
外企场景- arrow_right_alt
Allowing books to be rearranged arbitrarily changes the DP pattern and may require sorting strategies.
- arrow_right_alt
Using variable shelf widths for each level would require tracking multiple width states in DP.
- arrow_right_alt
Minimizing another metric, like total empty shelf space, shifts the state transition conditions.