题目描述
思路解析
一句话答案：LeetCode 1105 填充书架：书按顺序上架、每层厚度和不超 shelfWidth、层高取该层最高的书，求总高最小。一维 DP，f[i]=前 i 本最小总高，枚举最后一层从第几本起来转移，时间 O(n²)、空间 O(n)。
书按顺序上架，怎么分层才能让书架最矮
给一排书 books，每本是 [厚度、高度]，书架宽度 shelfWidth。书按给定顺序摆、不能打乱；同层厚度之和不超过 shelfWidth，放不下就另起一层。层高是这层最高那本的高度，总高是各层相加，求最小总高。演示 books=[[1,3],[2,1],[2,3],[1,4],[2,2]]、shelfWidth=4，答案 9。
为什么不能把每种分层方式都试一遍
每两本相邻的书之间都能选「断开」或「连一层」，n 本就有 2ⁿ⁻¹ 种分法，逐一算指数级炸开，且大量分法共享前缀被反复重算。既然「前 i 本怎么摆最矮」能独立回答，算一次存下来复用，就是动态规划（把『前 i 本书怎么摆最矮』算一次存下、后面直接取）。
状态定义：f[i] 存什么，f[0] 为什么是 0
定义 f[i] 为「前 i 本摆完能做到的最小总高」（把答案记进第 i 格，要用直接取）。下标 i 数的是书的本数、不是位置。f[0]=0：一本没摆、高度为 0，给后面递推（拿前面算好的推出后面的）当地基。答案是 f[n]。
转移（从前面算好的格子推出这一格）：枚举最后一层从哪本起
算 f[i] 只盯最后一层装哪几本连续的书。设它从第 j 本到第 i 本，前 j-1 本取最优 f[j-1]，这层层高是第 j 到 i 本里最高那本，于是 f[i] = f[j-1] + 这层最大高度。先给保底 f[i] = f[i-1] + 它的高度。
再让最后一层从第 i 本往左扩，累加新并那本的厚度。一旦超过 shelfWidth 就直接停（厚度只增不减、再往左更宽，一超即停）。没超就用 max 把层高更新成段内最高的一本，拿 f[j-1] + 层高刷新 f[i] 取更小。
拿这 5 本书把 f 表从左填到右
厚度 1、2、2、1、2，高度 3、1、3、4、2，shelfWidth=4，f[0]=0。
f[1]=f[0]+3=3。f[2]：保底 4；并第 1、2 本厚 3、层高 3，得 f[0]+3=3，f[2]=3。f[3]：保底 6；并第 2、3 本厚 4、层高 3 得 6 不更小，再并第 1 本厚 5 超宽停，f[3]=6。
f[4]：保底 10；并第 3、4 本厚 3、层高 max(4,3)=4，得 f[2]+4=7，f[4]=7。f[5]：保底 9；并第 4、5 本厚 3、层高 max(2,4)=4 得 10 不更小，f[5]=9 即答案，分层 [书1,书2]、[书3,书4]、[书5]。
漏了取 max、层高用成刚并进那本，总高为什么会算矮
外层 i 走 n 本、内层最坏从第 i 本往左扫到第 1 本，每格 O(n)，合起来时间 O(n²)（大 O 记号，描述规模变大时操作数大概怎么涨）；书厚时内层很快 break。空间只额外开长度 n+1 的数组 f，是 O(n)。
边界：全部塞一层时层高是最高那本；只有一本时答案是它的高度；厚度恰好等于 shelfWidth 也算放得下，判断用「超过才停」而非「大于等于就停」；超宽别写成「跳过往左」，该 break 不 break 会算进非法分层。
漏了 max、用刚并那本的高度，就把某层算矮。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
套路就一句:枚举「最后一层装哪几本连续的书」。最后一层选定后,前面那些书就是规模更小的同一个问题 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题