题目描述
思路解析动画文字版
套路就一句:枚举「最后一层装哪几本连续的书」。最后一层选定后,前面那些书就是规模更小的同一个问题 f[j-1],加上这一层的层高即可。下面把 f 表一格一格填出来。
先把数据摆出来。上面 5 个格子是 5 本书的高度,分别是 3、1、3、4、2;它们的厚度写在下面那行,依次是 1、2、2、1、2;书架宽度是 4。记住每本书是 [厚度, 高度] 一对值,厚度决定能不能挤进同一层,高度决定那层多高。
搭一张表,只有一行,列从左到右是 f[0] 到 f[5]。最左边 f[0] 先填 0:一本书都没摆,高度自然是 0。它是后面所有递推的地基。我们从 f[1] 往右一格一格填。
算 f[1]。先给一个保底方案:让第 1 本书(厚 1、高 3)自己单独占最后一层。那总高就是「前 0 本的最优」f[0]=0 再加上它自己的高 3,等于 3。先把这个值记进 f[1],下面看能不能把它跟前面的书拼一层、拼出更矮的。
所有放法都比过了,f[1] 最终是 3,意思是把前 1 本书摆完,书架最矮能做到 3。这格定死,继续往右算下一格。
算 f[2]。先给一个保底方案:让第 2 本书(厚 2、高 1)自己单独占最后一层。那总高就是「前 1 本的最优」f[1]=3 再加上它自己的高 1,等于 4。先把这个值记进 f[2],下面看能不能把它跟前面的书拼一层、拼出更矮的。
试着把第 1 到第 2 本书放在同一层。它们厚度之和是 3,没超过 4,能放;这一层的高度取这几本里最高的,是 3。那么总高 = 前 0 本的最优 f[0]=0 加上这层高 3,等于 3。它比刚才记的还小,把 f[2] 刷新成 3。
所有放法都比过了,f[2] 最终是 3,意思是把前 2 本书摆完,书架最矮能做到 3。这格定死,继续往右算下一格。
算 f[3]。先给一个保底方案:让第 3 本书(厚 2、高 3)自己单独占最后一层。那总高就是「前 2 本的最优」f[2]=3 再加上它自己的高 3,等于 6。先把这个值记进 f[3],下面看能不能把它跟前面的书拼一层、拼出更矮的。
试着把第 2 到第 3 本书放在同一层。它们厚度之和是 4,没超过 4,能放;这一层的高度取这几本里最高的,是 3。那么总高 = 前 1 本的最优 f[1]=3 加上这层高 3,等于 6。它没有更小,f[3] 还是 6,不动。
想把更前面的第 1 本书也并进这最后一层,可这层厚度加起来变成 5,超过了书架宽度 4,这本书挤不进来。再往左只会更宽,所以不用看了,f[3] 的扩展到此为止。
所有放法都比过了,f[3] 最终是 6,意思是把前 3 本书摆完,书架最矮能做到 6。这格定死,继续往右算下一格。
算 f[4]。先给一个保底方案:让第 4 本书(厚 1、高 4)自己单独占最后一层。那总高就是「前 3 本的最优」f[3]=6 再加上它自己的高 4,等于 10。先把这个值记进 f[4],下面看能不能把它跟前面的书拼一层、拼出更矮的。
试着把第 3 到第 4 本书放在同一层。它们厚度之和是 3,没超过 4,能放;这一层的高度取这几本里最高的,是 4。那么总高 = 前 2 本的最优 f[2]=3 加上这层高 4,等于 7。它比刚才记的还小,把 f[4] 刷新成 7。
想把更前面的第 2 本书也并进这最后一层,可这层厚度加起来变成 5,超过了书架宽度 4,这本书挤不进来。再往左只会更宽,所以不用看了,f[4] 的扩展到此为止。
所有放法都比过了,f[4] 最终是 7,意思是把前 4 本书摆完,书架最矮能做到 7。这格定死,继续往右算下一格。
算 f[5]。先给一个保底方案:让第 5 本书(厚 2、高 2)自己单独占最后一层。那总高就是「前 4 本的最优」f[4]=7 再加上它自己的高 2,等于 9。先把这个值记进 f[5],下面看能不能把它跟前面的书拼一层、拼出更矮的。
试着把第 4 到第 5 本书放在同一层。它们厚度之和是 3,没超过 4,能放;这一层的高度取这几本里最高的,是 4。那么总高 = 前 3 本的最优 f[3]=6 加上这层高 4,等于 10。它没有更小,f[5] 还是 9,不动。
想把更前面的第 3 本书也并进这最后一层,可这层厚度加起来变成 5,超过了书架宽度 4,这本书挤不进来。再往左只会更宽,所以不用看了,f[5] 的扩展到此为止。
所有放法都比过了,f[5] 最终是 9,意思是把前 5 本书摆完,书架最矮能做到 9。这格定死,表已经填完,下一步读出答案。
整张表填完了。最右边 f[5] 就是把 5 本书全部摆完的最小总高度,等于 9,这正是题目要的答案。回头看一眼这张表是怎么一步步长出来的:每一格都靠它左边某一格加上最后一层的层高得来。
顺着每格当初选的方案倒推一遍分层:f[5]=9 是让书5 单独成一层、接在 f[4] 后面;f[4]=7 是书3、书4 同一层(高 4)、接在 f[2] 后面;f[2]=3 是书1、书2 同一层(高 3)、接在 f[0] 后面。于是三层分别是 [书1,书2]、[书3,书4]、[书5]。
把最优分层标回原始的书上:绿色的书1、书2 是第一层,厚度 1+2=3 没超 4,层高取两本里高的 3;蓝色的书3、书4 是第二层,厚 2+1=3,层高 4;红色的书5 自己一层,层高 2。三层加起来 3+4+2=9,和 DP 表算出的答案严丝合缝。
边界先想清:全部塞一层时层高是最高那本、单本书答案就是它自己的高度、宽度恰好放满也算放得下。
面试重点:讲清为什么贪心不行(要枚举最后一层起点)、O(n²) 的来历、以及 f[0]=0 这个哨兵的作用。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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]复杂度
- 时间：O(n²)，n 是书的本数。外层 n 个 f[i],内层最坏从 i 一直往左扫到 1(书都很薄、宽度放得下),每个 f[i] 花 O(n),合起来 O(n²);书厚时内层很快超宽 break,实际更快
- 空间：O(n)，只用一个长度 n+1 的一维数组 f,峰值就是这条数组;没有递归栈,与本数线性相关
易错点
面试追问把动画讲成自己的话
追问为什么这题要用 DP,不能贪心地让每一层尽量塞满?
追问时间复杂度为什么是 O(n²)?
追问f 数组为什么要开 n+1 长、并且 f[0]=0?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
叶值的最小代价生成树
LeetCode 1130 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题