鸡蛋掉落问题是我在深圳大学算法设计与分析这门课里印象最深的一道动态规划题。它只有两句话的题面却能同时卡住三种人看不懂状态该怎么定义的、推得出方程但复杂度爆炸的、代码写对了却在边界上反复翻车的。如果你正在做实验四或者正在啃动态规划这一章我建议把这道题当成一个分水岭——它把用状态描述决策过程这件事讲得比 01 背包透彻得多。这篇文章我会从题目本身讲起把三种主流解法二维递推、换状态定义的一维滚动数组、内层二分优化的推导过程、代码实现、复杂度计算全部摊开顺便把我自己调试时踩到的坑整理成速查表。看完之后你至少能做到两件事拿到任意 k 和 n 都能在毫秒级算出答案并且能对着代码讲清楚每一行为什么这么写。适合已经学过递归和基础 DP、正在准备课程实验或者刷动态规划题的同学。1. 先把题目读三遍鸡蛋掉落到底在问什么1.1 题面复述与三个不能忽略的边界标准题面是这样的给定 k 枚完全相同的鸡蛋和 n 层楼已知存在一个临界楼层 f0 ≤ f ≤ n满足两个条件——从高于 f 的楼层扔下鸡蛋一定会碎从 f 层或者比 f 更低的楼层扔下一定不会碎。每次操作你可以选一枚还没碎的鸡蛋从任意楼层 x1 ≤ x ≤ n扔下去。求在最坏情况下确定 f 的确切值所需要的最少操作次数。这段描述里有三个特别容易被跳过、但直接决定答案对错的边界。第一个是 f 可以等于 0意思是鸡蛋从 1 楼扔下去就碎也是一种合法情况第二个是 f 可以等于 n意思是鸡蛋从顶楼扔下去仍然完好同样成立第三个是鸡蛋碎一枚就少一枚没碎的可以捡回来继续用。前两条决定了我们要区分的状态总数其实是 n 1 种f 取 0 到 n而不是 n 种。很多人第一次写代码时把 f 的取值范围当成 1 到 n结果就是答案比正确答案大 1 或者小 1。我当时的做法是先在纸上画一条 n 1 个格子的数轴把每次投掷得到的两种结果和每个结果对应哪一段格子画清楚再动手写状态转移。这一步花不了五分钟但能省掉后面半小时的调试。1.2 为什么第一反应是二分但二分在鸡蛋问题上会翻车几乎所有人看到求最少次数的第一反应都是二分查找从中间楼层扔一颗碎了就往低处找没碎就往高处找最多 log2(n) 次搞定。这个直觉在鸡蛋无限的前提下是对的问题就出在鸡蛋是消耗品。举个极端的例子k 1、n 100。你只有一个鸡蛋如果第一次就扔在 50 楼而且碎了那这个鸡蛋就没了你手上没有任何工具f 到底是多少你永远测不出来。所以只有一个鸡蛋时你唯一的策略是从 1 楼开始一层一层往上试最坏情况下要试 100 次。这说明投掷次数和剩余鸡蛋数是一对互相制约的资源二分的效率优势会被鸡蛋的消耗抵消掉。更精确地说第一枚鸡蛋扔在 x 层之后会分裂成两个子问题碎了的话剩下 k - 1 枚鸡蛋要在 x - 1 层里确定答案没碎的话剩下 k 枚鸡蛋要在上面 n - x 层里确定答案。取两者中更坏的那个再对所有可能的 x 取最优就得到了这道题的核心结构T(k, n) 1 min over x in [1, n] of max( T(k - 1, x - 1), T(k, n - x) )这个式子我建议你先抄在草稿纸上。它有两个特征外层是 min、内层是 max也就是在对手最坏情况选择之后我选最优策略。这类 min-max 结构在动态规划里非常常见也是这道题区别于 01 背包那种求和型DP 的关键点。1.3 状态里必须同时装下鸡蛋数和楼层数有了上面的递推式状态定义就顺理成章了令 dp[i][j] 表示手上还有 i 枚鸡蛋、需要在 j 层楼的范围内确定答案时所需的最少投掷次数。边界是 dp[1][j] j只剩一枚鸡蛋只能线性扫dp[i][0] 0没有楼层要测答案就是 0dp[i][1] 1只有一层扔一次就知道 f 是 0 还是 1。注意这里的 j 表示的是楼层区间长度不是绝对楼层号。这个细节很重要因为鸡蛋碎了之后我们关心的是下面这一段有多少层而不是绝对楼层是多少。把楼层号抽象成区间长度问题就从空间变成了规模这是动态规划里一个非常通用的降维手法。写到这里一个朴素解法的复杂度就出来了状态数是 O(k × n)每个状态要枚举 x内层 O(n)总体 O(k × n²)。当 n 达到 10⁴ 时这个数字是 10¹² 量级任何语言都跑不动。所以接下来真正要解决的问题不是怎么写出转移方程而是怎么把这个内层枚举干掉。2. 换一个状态定义复杂度直接降一维2.1 dp2[i][j] 的定义从求最小次数改成求最大覆盖上面那版 DP 之所以慢是因为我们把次数当成了要求的目标于是不得不枚举第一颗鸡蛋扔在哪里。如果反过来想——固定鸡蛋数和投掷次数最多能覆盖多少层楼——问题就变成了一个纯计数问题。定义 dp2[i][j] 为手上 i 枚鸡蛋允许投掷 j 次最多能够唯一确定多少层楼以内的答案。注意这里的层指的是楼层区间长度。转移的推导非常漂亮假设第一次投掷在某个楼层这一层会把这个区间切成三段。投掷的那一层本身无论碎还是不碎它的状态都能被唯一确定碎了说明 f 比它低没碎说明 f 不低于它反正这一层被吸收掉了所以先贡献 1。如果鸡蛋碎了我们损失一枚鸡蛋和一次机会还能往下面覆盖 dp2[i-1][j-1] 层如果没碎鸡蛋数不变但次数减一还能往上面覆盖 dp2[i][j-1] 层。于是dp2[i][j] dp2[i][j - 1] dp2[i - 1][j - 1] 1这里的 1 就是被投掷的那一层。写成更直观的形式dp2[i][j] dp2[i][j-1]上面那段 dp2[i-1][j-1]下面那段 1投掷的那一层。2.2 为什么这个转移是 O(1) 的对比一下两版转移第一版的 min over x 是一个枚举因为要选最优的投掷楼层第二版里投掷楼层被隐式地放到了区间的中点我们根本不需要枚举它——只要算出在最优策略下j 次投掷能把多大范围完全覆盖答案楼层自然就被这个范围包住了。这是我的理解方式第一版 DP 是在问给定规模最少花多少代价第二版是在问给定代价最多能办多大事。两者是同一个问题的正反两面但后者的转移是常数时间的因为它把枚举决策这一步挪到了状态的语义里。这个技巧在算法设计里反复出现比如n 个数里最多选多少个使得和不超过 W和恰好选 m 个数最少需要多大容量往往是后者更好算。边界条件是dp2[0][j] 0没有鸡蛋一层都测不了dp2[i][0] 0没有投掷次数同样一层都测不了dp2[i][1] 1只有一次机会只能测 1 层也就是直接扔一次确认这一层。不变量是 dp2[i][j] 关于 i 和 j 都是单调不减的。2.3 答案怎么取循环什么时候停有了 dp2 之后原问题的答案就是最小的 j使得 dp2[k][j] ≥ n。因为我们要覆盖 n 层楼的全部 n 1 种可能情况只要覆盖能力达到 n 就够了。实现上不需要开二维数组。观察转移式 dp2[i][j] dp2[i][j-1] dp2[i-1][j-1] 1等号右边用到的 dp2[·][j-1] 全是上一轮的值所以完全可以用一个一维数组 dp[i] 滚动更新dp[i] 在更新前代表 dp2[i][j-1]更新后代表 dp2[i][j]。这就是后面代码里那三行的由来。还有个细节值得单独提一下如果 dp2 的值会无上限增长鸡蛋多、次数多的时候它是指数级的用 Python 或 Java 的 64 位整数都够用因为循环在 dp2[k][j] ≥ n 时就停了最多超出 n 一点点。但如果用 C 的 int 就存在理论上的溢出风险保险起见用 long long。3. 上机实操从记忆化搜索到一维滚动数组的四版代码3.1 第一版记忆化递归用来验证思路这一版不追求性能追求能对上那张手推的表。你可以用它把 dp[i][j] 的转移逻辑跑通然后拿它当标程去对拍后面的快速版本。import sys from functools import lru_cache def egg_drop_memo(k, n): sys.setrecursionlimit(200000) lru_cache(maxsizeNone) def solve(eggs, floors): if floors 1: return floors # 0 层不用试1 层试 1 次 if eggs 1: return floors # 只剩一枚只能从下往上线性试 best floors # 线性扫描是一个合法上界 for x in range(1, floors 1): left solve(eggs - 1, x - 1) # 碎了往下面查 if left best: # 剪枝left 关于 x 单调递增 break right solve(eggs, floors - x) # 没碎往上面查 cur 1 max(left, right) if cur best: best cur return best return solve(k, n)这段代码里有三个地方值得说。第一if floors 1放在if eggs 1前面保证 floors 0 时直接返回 0 而不进入循环第二best floors这个初始值不是随手写的因为从 1 楼开始一层层往上试永远是一个合法策略所以 floors 一定是一个有效上界第三那句if left best: break是本层唯一能救命的剪枝——left 随着 x 增大而单调递增一旦 left 已经不小于当前最优值后面所有 x 都不可能更好直接跳出。没有这句剪枝n 稍大一点就跑到天荒地老。3.2 第二版二维递推实验报告里最好写的一版如果你的实验报告要求写伪代码和复杂度分析二维递推版是最容易讲清楚的因为它和自然语言描述几乎一一对应。def egg_drop_dp(k, n): if n 0: return 0 # dp[i][j]: i 枚鸡蛋需要确定 j 层楼范围内的答案最少投掷次数 dp [[0] * (n 1) for _ in range(k 1)] for j in range(1, n 1): dp[1][j] j # 只有一枚鸡蛋线性扫描 for i in range(2, k 1): for j in range(1, n 1): dp[i][j] j # 用线性扫描当上界 for x in range(1, j 1): if dp[i - 1][x - 1] dp[i][j]: break # 左半部分已经不可能更优了 cur 1 max(dp[i - 1][x - 1], dp[i][j - x]) if cur dp[i][j]: dp[i][j] cur return dp[k][n]写的时候有两个坑。一个是k 1要在循环外单独填好因为递推从i 2开始如果 k 本身就等于 1后面的循环一次都不会执行dp[1][n]必须提前是正确值。另一个是dp[i][j-x]的下标因为x ≥ 1所以j - x ≤ j - 1 j说明它在同一行内是已经算过的不会出现用自己算自己的循环依赖。理论复杂度是 O(k × n²)但由于那句 break 剪枝实测在 n ≤ 1000 的时候还算能忍一旦 n 上到 10⁴ 就彻底不行了。3.3 第三版一维滚动数组实测能过全部数据点这是我最终交上去的版本也是我最推荐背下来的那一版。核心就是把第二节的 dp2 用一维数组滚动代码短到只有十来行。import math def egg_drop_fast(k, n): if n 0: return 0 # 特判鸡蛋足够多时退化为标准二分查找 m 0 cover 0 # cover 2^m - 1 while cover n: m 1 cover cover * 2 1 if k m: return m # dp[i]: i 枚鸡蛋、当前轮次数下能覆盖的最大楼层数 dp [0] * (k 1) t 0 while dp[k] n: t 1 for i in range(k, 0, -1): # 必须倒序 dp[i] dp[i] dp[i - 1] 1 return tfor i in range(k, 0, -1)这个倒序是整个算法的命门我后面会专门用一节来讲它为什么必须是倒序。整段代码的时间复杂度是 O(k × m)其中 m 是最终答案的次数空间复杂度只有 O(k)。那个特判也不能省。当 k 很大、n 相对较小时比如 k 100、n 100如果不特判内层循环每轮要跑 100 次而实际只需要跑 8 轮左右虽然也不慢但当 k 达到 10⁵ 级别时就会明显拖后腿。用k m提前返回等于把 k 截断到 log₂(n1) 的量级内层循环直接缩水一个数量级以上。3.4 第四版内层二分优化以及它其实不该用第二版最慢的地方是内层枚举 x。观察一下cur(x) 1 max(dp[i-1][x-1], dp[i][j-x])这个函数dp[i-1][x-1]关于 x 单调递增dp[i][j-x]关于 x 单调递减两者取 max 之后是一条先降后升的曲线最小值出现在两条曲线的交叉点附近。既然是单峰结构就可以二分找交叉点把内层从 O(n) 压到 O(log n)。def egg_drop_bisect(k, n): if n 0: return 0 dp [[0] * (n 1) for _ in range(k 1)] for j in range(1, n 1): dp[1][j] j for i in range(2, k 1): for j in range(1, n 1): lo, hi 1, j # 找第一个满足 dp[i-1][x-1] dp[i][j-x] 的 x while lo hi: mid (lo hi) // 2 if dp[i - 1][mid - 1] dp[i][j - mid]: lo mid 1 else: hi mid best 1 max(dp[i - 1][lo - 1], dp[i][j - lo]) if lo 1: cand 1 max(dp[i - 1][lo - 2], dp[i][j - lo 1]) if cand best: best cand dp[i][j] best return dp[k][n]复杂度是 O(k × n × log n)。看着比 O(k × n²) 好很多但在 n 10⁴、k 100 的时候是 1.4 × 10⁷ 次操作纯 Python 跑下来要几十秒还不如第三版跑得快第三版同规模只要不到两千次操作。所以我的实际建议是这一版写进实验报告里当优化思路加分但真正提交运行的时候用第三版。4. 复杂度推演与参数计算把数字算给老师看4.1 O(k × m) 里的 m 到底有多大老师最常问的问题就是你这个算法的最坏复杂度是多少。第三版代码的循环次数是 k × m所以关键就在 m 的量级上。m 是最终答案也就是所需的最少投掷次数。它的增长规律很有意思当 k 1 时m n线性扫描最坏情况。当 k 2 时dp2[2][m] C(m,1) C(m,2) m(m1)/2也就是三角数。解 m(m1)/2 ≥ n得到 m ≈ √(2n)。当 k ≥ m 时dp2[k][m] 2^m - 1也就是完全二叉树能覆盖的节点数m ⌈log₂(n1)⌉。中间那一段比如 k 3、4、5可以用组合数求和公式算dp2[k][m] Σ C(m, t)t 从 1 到 min(k, m)。我把 n 10000 时不同 k 对应的 m 实算了一遍数据如下鸡蛋数 k覆盖 10000 层所需的最少操作数 m对应公式110000m2141m(m1)/2 ≥ 10000340m C(m,2) C(m,3) ≥ 10000423四项组合数和 ≥ 10000518五项组合数和 ≥ 10000≥ 14142^m − 1 ≥ 10000这张表最值得看的地方是边际收益递减鸡蛋从 1 枚加到 2 枚操作数从 10000 暴降到 141从 2 枚加到 3 枚降到 40再加到 4 枚、5 枚收益明显变小到 14 枚以后就完全饱和了再加鸡蛋也不会让答案变小。这个规律本身就解释了为什么那道特判是合理的——鸡蛋超过 log₂(n1) 之后就是纯浪费。顺带说一个能写进报告的小结论当 k 2 时答案是满足 m(m1)/2 ≥ n 的最小整数 m闭式解是 m ⌈(√(8n1) − 1) / 2⌉当 k 3 时答案是满足 m(m² 5)/6 ≥ n 的最小整数 m。这两个公式可以让你的报告看起来扎实很多。4.2 空间复杂度与 Python 的实际内存占用第三版只用了一个长度为 k 1 的列表空间复杂度 O(k)换算成实际内存在 k 被截断到 ⌈log₂(n1)⌉ 之后基本上就是几十个整数可以忽略不计。第二版要开 (k1) × (n1) 的二维表n 10⁴、k 100 时是 10⁶ 个单元Python 里每个 int 对象大约 28 字节加上 list 的指针数组实际占用在 40 MB 上下接近很多评测机的内存上限。这里有个经验Python 里存整数列表用array模块或者numpy能省不少内存但在这个题的规模下完全没必要直接换第三版更省事。如果实验报告里必须分析第二版的空间就老老实实写 O(k × n)然后补一句可用滚动数组优化到 O(k)这样既有分析又有优化意识。4.3 三版代码在同一台机器上的实测对比我在本地用 k 100、n 10000 这组数据跑了一遍Python 3.11普通笔记本结果如下版本理论复杂度实测耗时是否能过记忆化递归指数级带剪枝后接近 O(k × n²)直接 RecursionError调大递归深度后 30 秒以上没跑完不能二维递推O(k × n²)剪枝后实测快很多约 45 秒不能内层二分O(k × n × log n)约 22 秒勉强但体验很差一维滚动O(k × m)k 被截断到 14小于 1 毫秒完全没问题这个对比特别适合放报告里它直观地说明了换状态定义这一手比优化常数的收益高多少个数量级。从 45 秒到 0.001 秒靠的不是写得更紧凑而是换了个问题来算。5. 测试用例设计自造数据把代码逼到墙角5.1 必测的九组数据很多人交实验的时候只跑老师给的样例样例过了就以为万事大吉。我的习惯是自己设计一组能覆盖所有分支的数据下面这九组是我每次做这道题都会跑的编号kn期望输出这组数据在测什么1111最小非零规模211010单鸡蛋退化只能线性3263课本经典样例手算可验证4210014三角数公式验证53144组合数覆盖验证62100045中等规模性能71001000014鸡蛋过剩走特判分支8500零层楼边界9501000014大数据量正确性 性能双查第 3 组和第 5 组是能徒手验算的出错了立刻能定位。第 4 组我特别推荐k 2 时答案就是三角数m 13 覆盖 91 层m 14 覆盖 105 层所以 100 层的答案是 14这个推导过程可以直接写进实验报告当作算法正确性的验证。第 6 组 45 也是同理44 × 45 / 2 990 100045 × 46 / 2 1035 ≥ 1000。5.2 边界与极端值三类必须单独测的输入第一类是 n 0。这个输入下没有楼层需要确定答案应该是 0。如果你的代码在while dp[k] n之前先t 1就会返回 1差一位。我建议在函数最开头就把if n 0: return 0单独写出来。第二类是 k 0 且 n 0。数学上这是无解的没有鸡蛋永远测不出来但大多数题目保证 k ≥ 1所以可以不做处理但报告里最好提一句本算法假设 k ≥ 1显得你考虑过。第三类是 k 远大于 n。比如 k 10⁵、n 1这时特判分支会直接返回 1同时避免了内层循环跑十万次。这类数据是性能测试里的常客出题人特别喜欢用它来卡那些忘记截断 k 的写法。5.3 用暴力版当标程做对拍自己写的代码自己测很容易因为知道答案所以看不出错误。我用的办法是把 3.1 节的记忆化递归版当标程随机生成一批小规模数据k 在 1 到 5 之间n 在 0 到 200 之间两个程序同时跑逐个比对输出。只要有一组对不上就立刻把这组输入单独拎出来手推。import random for _ in range(500): k random.randint(1, 5) n random.randint(0, 200) a egg_drop_memo(k, n) b egg_drop_fast(k, n) if a ! b: print(不一致, k, n, a, b) break else: print(500 组随机数据全部通过)这十几行代码把我在边界上的所有问题都暴露出来了包括那个忘了处理 n 0的错误。做实验的时候多花五分钟写对拍比盯着屏幕猜哪里错了要高效得多。6. 踩坑记录那些让你反复提交错误的细节6.1 一维数组的遍历方向是这道题最大的陷阱第三版代码里那句for i in range(k, 0, -1)我第一遍写的时候写成了正序结果答案在小规模数据上碰巧对一到大 k 就偏小。原因拆开看转移式是 dp2[i][j] dp2[i][j-1] dp2[i-1][j-1] 1等号右边的两个量都属于上一轮也就是 j-1 次投掷的状态而数组 dp[i] 在更新前保留的正是上一轮的值。正序遍历时先算 dp[1]把 dp[1] 从上一轮改成了这一轮接着算 dp[2] 时用到的 dp[1] 已经是本轮的新值了等于把 dp2[i-1][j] 当成了 dp2[i-1][j-1] 用多算了一层结果偏大或者偏小的方向取决于具体数据非常隐蔽。倒序遍历时算 dp[i] 时 dp[i-1] 还没被本轮碰过用的就是干净的上一轮值。这个规律可以总结成一句话一维滚动数组的遍历方向永远让被依赖的那一项保持上一轮的值。如果依赖的是更小的下标就倒序如果依赖的是更大的下标就正序如果依赖的是自身比如完全背包就从依赖的下标开始正序。这个规则在 01 背包、完全背包、最长公共子序列的空间优化里全都通用。6.2 状态定义混用导致的隐性错误另一个常见的坑是在同一份代码里混用两套状态语义。比如前面用 dp[i][j] 表示i 枚鸡蛋确定 j 层的最少次数后面写转移时手一滑把 dp[i-1][x-1] 理解成了i-1 枚鸡蛋覆盖 x-1 层两种理解下的边界和增量都不一样代码不会报错但答案会系统性偏移。我的防护办法是把状态含义写在函数开头的注释里每次改代码前先读一遍那行注释。听起来很笨但确实有效。另外建议给两套实现的变量取不同的名字比如第一套用dp_min第二套用dp_cover从命名上就杜绝混用。6.3 递归版的两个隐蔽问题第一个是 Python 的默认递归深度只有 1000。记忆化递归版在 n 稍大时递归栈深度会随着 floors 减小而线性增长很容易触发 RecursionError。解决方式是sys.setrecursionlimit(200000)但要注意这个数字不能无脑开太大栈溢出会直接把进程干掉而不是抛异常。第二个是lru_cache的缓存键。如果参数里混进了列表或者可变对象缓存会直接失效程序会退化到指数复杂度。这道题的参数都是整数一般不会踩到但如果你把 floors 换成一个区间元组来表示任意区间有些变体题会这么干就要注意元组是不可变的缓存是安全的但缓存命中率会明显下降。6.4 常见问题速查表现象大概率原因排查动作小数据对大数据偏小一维数组正序遍历检查内层循环方向是否倒序答案比标准答案大 1n 0 时先自增了 t在函数开头单独返回 0大 k 时程序很慢没有截断 k加上 k ≥ m 时的提前返回报 RecursionError递归深度超限设置递归上限或改写成递推二维版本内存超限开了 (k1) × (n1) 的表换成滚动数组空间降到 O(k)递推版跑到一半超时内层 O(n) 枚举换第二套状态定义或加剪枝结果全部偏大边界 dp[i][1] 没初始化检查只有一层时的返回值C 提交答案离谱int 溢出把 dp 数组换成 long long这张表里最值得记住的是第一行和第二行它们覆盖了我遇到过的八成问题。7. 迁移训练鸡蛋掉落和 01 背包、车辆调度用的是同一套模板7.1 一维滚动数组的通用判断规则前面已经说过遍历方向的问题这里把它提炼成一条可复用的规则先写出二维转移式看清楚等号右边每个项是上一行同列、上一行前列还是本行前列。如果用到的是上一行同列和上一行前列比如 01 背包的 dp[j] max(dp[j], dp[j - w] v)那内层就要倒序遍历容量保证 dp[j - w] 还是上一行的值。如果用到的是本行前列比如完全背包的 dp[j] max(dp[j], dp[j - w] v)那就要正序遍历让 dp[j - w] 更新成本行的值。鸡蛋掉落的滚动是倒序遍历鸡蛋数因为依赖的 dp[i - 1] 是上一轮的。这几种情形看着五花八门其实判断标准只有一条看依赖项属于哪一行/哪一轮然后让遍历顺序保证它在该轮还没被覆盖。7.2 01 背包和鸡蛋掉落的对照把两个问题并排放能看到很多结构上的对应关系对比项鸡蛋掉落01 背包状态含义i 枚鸡蛋、j 层楼的最少次数前 i 件物品、容量 j 的最大价值二维转移dp[i][j] dp[i][j-1] dp[i-1][j-1] 1dp[i][j] max(dp[i-1][j], dp[i-1][j-w] v)一维优化dp[i] dp[i] dp[i-1] 1倒序 idp[j] max(dp[j], dp[j-w] v)倒序 j决策类型最优决策min-max最优决策max边界处理鸡蛋数或次数为 0 时返回 0前 0 件物品或容量为 0 时价值为 0常见变体求具体策略、求期望次数恰好装满、分组背包、多重背包写 01 背包的 Python 时最容易被忽略的是range(cap, weights[i] - 1, -1)里的终止位置——必须是weights[i] - 1因为j - weights[i]至少要等于 0写成了weights[i]就会漏掉恰好装满的那一种情况。这跟鸡蛋掉落里range(k, 0, -1)的终止位置必须是 0 是一个道理两边的下标边界都容易写错。def knapsack(weights, values, cap): dp [0] * (cap 1) for i in range(len(weights)): for j in range(cap, weights[i] - 1, -1): # 倒序且下界是 weights[i]-1 dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[cap]7.3 车辆调度类问题的建模切入点车辆动态规划这个词在算法课里通常指两类问题一类是路径规划类比如车辆从起点到终点每段路有油耗和速度限制求最小油耗或者最小时间另一类是车辆调度类比如有若干运输任务车辆有容量限制求最少用车数或者最小总成本。这两类问题的建模思路其实和鸡蛋掉落是一条线上的先问自己我有哪些资源是会被消耗的鸡蛋数、载重量、剩余油量我要覆盖或完成的目标是什么确定的楼层范围、所有任务然后定义状态为消耗了若干资源、完成了若干目标时的最优值。拿一个简化版的加油问题举例一辆车油箱容量 C从起点到终点依次经过 n 1 个站点第 i 站到第 i 1 站的距离是 d[i]第 i 站的油价是 p[i]。设 dp[i][j] 表示到达第 i 站时油箱还剩 j 升油的最小花费转移就是在第 i 站决定加多少油 k0 ≤ k ≤ C - j代价是 k × p[i]然后减掉这一段路的消耗。内层的 k 枚举同样是一个可以优化的点思路和鸡蛋掉落里的内层枚举优化完全一致——观察代价函数的单调性或凸性再决定用二分还是单调队列来压复杂度。把这三个问题摆在一起看你会发现动态规划的套路其实高度统一先把资源和目标两个维度定下来再写出这一步决策之后资源怎么变最后检查转移用的到底是上一轮还是本轮的表格。剩下的就是复杂度优化和边界处理这两件体力活了。最后分享一点我自己的体会。这道题我前后写废了四版代码真正卡住我的从来不是转移方程而是那句倒序遍历以及 n 0 的边界。后来我养成了一个习惯每写完一版 DP先不急着提交而是手推一个规模最小的用例把状态表在纸上画三行出来跟前一版对比。这个动作只要两分钟但能抓住绝大多数方向性错误。如果你也在做这个实验建议把 5.1 节那张表里的九组数据自己手推一遍再上机推完再去看代码很多坑其实根本不用踩。
鸡蛋掉落动态规划：状态定义、一维滚动与二分优化
鸡蛋掉落问题是我在深圳大学算法设计与分析这门课里印象最深的一道动态规划题。它只有两句话的题面却能同时卡住三种人看不懂状态该怎么定义的、推得出方程但复杂度爆炸的、代码写对了却在边界上反复翻车的。如果你正在做实验四或者正在啃动态规划这一章我建议把这道题当成一个分水岭——它把用状态描述决策过程这件事讲得比 01 背包透彻得多。这篇文章我会从题目本身讲起把三种主流解法二维递推、换状态定义的一维滚动数组、内层二分优化的推导过程、代码实现、复杂度计算全部摊开顺便把我自己调试时踩到的坑整理成速查表。看完之后你至少能做到两件事拿到任意 k 和 n 都能在毫秒级算出答案并且能对着代码讲清楚每一行为什么这么写。适合已经学过递归和基础 DP、正在准备课程实验或者刷动态规划题的同学。1. 先把题目读三遍鸡蛋掉落到底在问什么1.1 题面复述与三个不能忽略的边界标准题面是这样的给定 k 枚完全相同的鸡蛋和 n 层楼已知存在一个临界楼层 f0 ≤ f ≤ n满足两个条件——从高于 f 的楼层扔下鸡蛋一定会碎从 f 层或者比 f 更低的楼层扔下一定不会碎。每次操作你可以选一枚还没碎的鸡蛋从任意楼层 x1 ≤ x ≤ n扔下去。求在最坏情况下确定 f 的确切值所需要的最少操作次数。这段描述里有三个特别容易被跳过、但直接决定答案对错的边界。第一个是 f 可以等于 0意思是鸡蛋从 1 楼扔下去就碎也是一种合法情况第二个是 f 可以等于 n意思是鸡蛋从顶楼扔下去仍然完好同样成立第三个是鸡蛋碎一枚就少一枚没碎的可以捡回来继续用。前两条决定了我们要区分的状态总数其实是 n 1 种f 取 0 到 n而不是 n 种。很多人第一次写代码时把 f 的取值范围当成 1 到 n结果就是答案比正确答案大 1 或者小 1。我当时的做法是先在纸上画一条 n 1 个格子的数轴把每次投掷得到的两种结果和每个结果对应哪一段格子画清楚再动手写状态转移。这一步花不了五分钟但能省掉后面半小时的调试。1.2 为什么第一反应是二分但二分在鸡蛋问题上会翻车几乎所有人看到求最少次数的第一反应都是二分查找从中间楼层扔一颗碎了就往低处找没碎就往高处找最多 log2(n) 次搞定。这个直觉在鸡蛋无限的前提下是对的问题就出在鸡蛋是消耗品。举个极端的例子k 1、n 100。你只有一个鸡蛋如果第一次就扔在 50 楼而且碎了那这个鸡蛋就没了你手上没有任何工具f 到底是多少你永远测不出来。所以只有一个鸡蛋时你唯一的策略是从 1 楼开始一层一层往上试最坏情况下要试 100 次。这说明投掷次数和剩余鸡蛋数是一对互相制约的资源二分的效率优势会被鸡蛋的消耗抵消掉。更精确地说第一枚鸡蛋扔在 x 层之后会分裂成两个子问题碎了的话剩下 k - 1 枚鸡蛋要在 x - 1 层里确定答案没碎的话剩下 k 枚鸡蛋要在上面 n - x 层里确定答案。取两者中更坏的那个再对所有可能的 x 取最优就得到了这道题的核心结构T(k, n) 1 min over x in [1, n] of max( T(k - 1, x - 1), T(k, n - x) )这个式子我建议你先抄在草稿纸上。它有两个特征外层是 min、内层是 max也就是在对手最坏情况选择之后我选最优策略。这类 min-max 结构在动态规划里非常常见也是这道题区别于 01 背包那种求和型DP 的关键点。1.3 状态里必须同时装下鸡蛋数和楼层数有了上面的递推式状态定义就顺理成章了令 dp[i][j] 表示手上还有 i 枚鸡蛋、需要在 j 层楼的范围内确定答案时所需的最少投掷次数。边界是 dp[1][j] j只剩一枚鸡蛋只能线性扫dp[i][0] 0没有楼层要测答案就是 0dp[i][1] 1只有一层扔一次就知道 f 是 0 还是 1。注意这里的 j 表示的是楼层区间长度不是绝对楼层号。这个细节很重要因为鸡蛋碎了之后我们关心的是下面这一段有多少层而不是绝对楼层是多少。把楼层号抽象成区间长度问题就从空间变成了规模这是动态规划里一个非常通用的降维手法。写到这里一个朴素解法的复杂度就出来了状态数是 O(k × n)每个状态要枚举 x内层 O(n)总体 O(k × n²)。当 n 达到 10⁴ 时这个数字是 10¹² 量级任何语言都跑不动。所以接下来真正要解决的问题不是怎么写出转移方程而是怎么把这个内层枚举干掉。2. 换一个状态定义复杂度直接降一维2.1 dp2[i][j] 的定义从求最小次数改成求最大覆盖上面那版 DP 之所以慢是因为我们把次数当成了要求的目标于是不得不枚举第一颗鸡蛋扔在哪里。如果反过来想——固定鸡蛋数和投掷次数最多能覆盖多少层楼——问题就变成了一个纯计数问题。定义 dp2[i][j] 为手上 i 枚鸡蛋允许投掷 j 次最多能够唯一确定多少层楼以内的答案。注意这里的层指的是楼层区间长度。转移的推导非常漂亮假设第一次投掷在某个楼层这一层会把这个区间切成三段。投掷的那一层本身无论碎还是不碎它的状态都能被唯一确定碎了说明 f 比它低没碎说明 f 不低于它反正这一层被吸收掉了所以先贡献 1。如果鸡蛋碎了我们损失一枚鸡蛋和一次机会还能往下面覆盖 dp2[i-1][j-1] 层如果没碎鸡蛋数不变但次数减一还能往上面覆盖 dp2[i][j-1] 层。于是dp2[i][j] dp2[i][j - 1] dp2[i - 1][j - 1] 1这里的 1 就是被投掷的那一层。写成更直观的形式dp2[i][j] dp2[i][j-1]上面那段 dp2[i-1][j-1]下面那段 1投掷的那一层。2.2 为什么这个转移是 O(1) 的对比一下两版转移第一版的 min over x 是一个枚举因为要选最优的投掷楼层第二版里投掷楼层被隐式地放到了区间的中点我们根本不需要枚举它——只要算出在最优策略下j 次投掷能把多大范围完全覆盖答案楼层自然就被这个范围包住了。这是我的理解方式第一版 DP 是在问给定规模最少花多少代价第二版是在问给定代价最多能办多大事。两者是同一个问题的正反两面但后者的转移是常数时间的因为它把枚举决策这一步挪到了状态的语义里。这个技巧在算法设计里反复出现比如n 个数里最多选多少个使得和不超过 W和恰好选 m 个数最少需要多大容量往往是后者更好算。边界条件是dp2[0][j] 0没有鸡蛋一层都测不了dp2[i][0] 0没有投掷次数同样一层都测不了dp2[i][1] 1只有一次机会只能测 1 层也就是直接扔一次确认这一层。不变量是 dp2[i][j] 关于 i 和 j 都是单调不减的。2.3 答案怎么取循环什么时候停有了 dp2 之后原问题的答案就是最小的 j使得 dp2[k][j] ≥ n。因为我们要覆盖 n 层楼的全部 n 1 种可能情况只要覆盖能力达到 n 就够了。实现上不需要开二维数组。观察转移式 dp2[i][j] dp2[i][j-1] dp2[i-1][j-1] 1等号右边用到的 dp2[·][j-1] 全是上一轮的值所以完全可以用一个一维数组 dp[i] 滚动更新dp[i] 在更新前代表 dp2[i][j-1]更新后代表 dp2[i][j]。这就是后面代码里那三行的由来。还有个细节值得单独提一下如果 dp2 的值会无上限增长鸡蛋多、次数多的时候它是指数级的用 Python 或 Java 的 64 位整数都够用因为循环在 dp2[k][j] ≥ n 时就停了最多超出 n 一点点。但如果用 C 的 int 就存在理论上的溢出风险保险起见用 long long。3. 上机实操从记忆化搜索到一维滚动数组的四版代码3.1 第一版记忆化递归用来验证思路这一版不追求性能追求能对上那张手推的表。你可以用它把 dp[i][j] 的转移逻辑跑通然后拿它当标程去对拍后面的快速版本。import sys from functools import lru_cache def egg_drop_memo(k, n): sys.setrecursionlimit(200000) lru_cache(maxsizeNone) def solve(eggs, floors): if floors 1: return floors # 0 层不用试1 层试 1 次 if eggs 1: return floors # 只剩一枚只能从下往上线性试 best floors # 线性扫描是一个合法上界 for x in range(1, floors 1): left solve(eggs - 1, x - 1) # 碎了往下面查 if left best: # 剪枝left 关于 x 单调递增 break right solve(eggs, floors - x) # 没碎往上面查 cur 1 max(left, right) if cur best: best cur return best return solve(k, n)这段代码里有三个地方值得说。第一if floors 1放在if eggs 1前面保证 floors 0 时直接返回 0 而不进入循环第二best floors这个初始值不是随手写的因为从 1 楼开始一层层往上试永远是一个合法策略所以 floors 一定是一个有效上界第三那句if left best: break是本层唯一能救命的剪枝——left 随着 x 增大而单调递增一旦 left 已经不小于当前最优值后面所有 x 都不可能更好直接跳出。没有这句剪枝n 稍大一点就跑到天荒地老。3.2 第二版二维递推实验报告里最好写的一版如果你的实验报告要求写伪代码和复杂度分析二维递推版是最容易讲清楚的因为它和自然语言描述几乎一一对应。def egg_drop_dp(k, n): if n 0: return 0 # dp[i][j]: i 枚鸡蛋需要确定 j 层楼范围内的答案最少投掷次数 dp [[0] * (n 1) for _ in range(k 1)] for j in range(1, n 1): dp[1][j] j # 只有一枚鸡蛋线性扫描 for i in range(2, k 1): for j in range(1, n 1): dp[i][j] j # 用线性扫描当上界 for x in range(1, j 1): if dp[i - 1][x - 1] dp[i][j]: break # 左半部分已经不可能更优了 cur 1 max(dp[i - 1][x - 1], dp[i][j - x]) if cur dp[i][j]: dp[i][j] cur return dp[k][n]写的时候有两个坑。一个是k 1要在循环外单独填好因为递推从i 2开始如果 k 本身就等于 1后面的循环一次都不会执行dp[1][n]必须提前是正确值。另一个是dp[i][j-x]的下标因为x ≥ 1所以j - x ≤ j - 1 j说明它在同一行内是已经算过的不会出现用自己算自己的循环依赖。理论复杂度是 O(k × n²)但由于那句 break 剪枝实测在 n ≤ 1000 的时候还算能忍一旦 n 上到 10⁴ 就彻底不行了。3.3 第三版一维滚动数组实测能过全部数据点这是我最终交上去的版本也是我最推荐背下来的那一版。核心就是把第二节的 dp2 用一维数组滚动代码短到只有十来行。import math def egg_drop_fast(k, n): if n 0: return 0 # 特判鸡蛋足够多时退化为标准二分查找 m 0 cover 0 # cover 2^m - 1 while cover n: m 1 cover cover * 2 1 if k m: return m # dp[i]: i 枚鸡蛋、当前轮次数下能覆盖的最大楼层数 dp [0] * (k 1) t 0 while dp[k] n: t 1 for i in range(k, 0, -1): # 必须倒序 dp[i] dp[i] dp[i - 1] 1 return tfor i in range(k, 0, -1)这个倒序是整个算法的命门我后面会专门用一节来讲它为什么必须是倒序。整段代码的时间复杂度是 O(k × m)其中 m 是最终答案的次数空间复杂度只有 O(k)。那个特判也不能省。当 k 很大、n 相对较小时比如 k 100、n 100如果不特判内层循环每轮要跑 100 次而实际只需要跑 8 轮左右虽然也不慢但当 k 达到 10⁵ 级别时就会明显拖后腿。用k m提前返回等于把 k 截断到 log₂(n1) 的量级内层循环直接缩水一个数量级以上。3.4 第四版内层二分优化以及它其实不该用第二版最慢的地方是内层枚举 x。观察一下cur(x) 1 max(dp[i-1][x-1], dp[i][j-x])这个函数dp[i-1][x-1]关于 x 单调递增dp[i][j-x]关于 x 单调递减两者取 max 之后是一条先降后升的曲线最小值出现在两条曲线的交叉点附近。既然是单峰结构就可以二分找交叉点把内层从 O(n) 压到 O(log n)。def egg_drop_bisect(k, n): if n 0: return 0 dp [[0] * (n 1) for _ in range(k 1)] for j in range(1, n 1): dp[1][j] j for i in range(2, k 1): for j in range(1, n 1): lo, hi 1, j # 找第一个满足 dp[i-1][x-1] dp[i][j-x] 的 x while lo hi: mid (lo hi) // 2 if dp[i - 1][mid - 1] dp[i][j - mid]: lo mid 1 else: hi mid best 1 max(dp[i - 1][lo - 1], dp[i][j - lo]) if lo 1: cand 1 max(dp[i - 1][lo - 2], dp[i][j - lo 1]) if cand best: best cand dp[i][j] best return dp[k][n]复杂度是 O(k × n × log n)。看着比 O(k × n²) 好很多但在 n 10⁴、k 100 的时候是 1.4 × 10⁷ 次操作纯 Python 跑下来要几十秒还不如第三版跑得快第三版同规模只要不到两千次操作。所以我的实际建议是这一版写进实验报告里当优化思路加分但真正提交运行的时候用第三版。4. 复杂度推演与参数计算把数字算给老师看4.1 O(k × m) 里的 m 到底有多大老师最常问的问题就是你这个算法的最坏复杂度是多少。第三版代码的循环次数是 k × m所以关键就在 m 的量级上。m 是最终答案也就是所需的最少投掷次数。它的增长规律很有意思当 k 1 时m n线性扫描最坏情况。当 k 2 时dp2[2][m] C(m,1) C(m,2) m(m1)/2也就是三角数。解 m(m1)/2 ≥ n得到 m ≈ √(2n)。当 k ≥ m 时dp2[k][m] 2^m - 1也就是完全二叉树能覆盖的节点数m ⌈log₂(n1)⌉。中间那一段比如 k 3、4、5可以用组合数求和公式算dp2[k][m] Σ C(m, t)t 从 1 到 min(k, m)。我把 n 10000 时不同 k 对应的 m 实算了一遍数据如下鸡蛋数 k覆盖 10000 层所需的最少操作数 m对应公式110000m2141m(m1)/2 ≥ 10000340m C(m,2) C(m,3) ≥ 10000423四项组合数和 ≥ 10000518五项组合数和 ≥ 10000≥ 14142^m − 1 ≥ 10000这张表最值得看的地方是边际收益递减鸡蛋从 1 枚加到 2 枚操作数从 10000 暴降到 141从 2 枚加到 3 枚降到 40再加到 4 枚、5 枚收益明显变小到 14 枚以后就完全饱和了再加鸡蛋也不会让答案变小。这个规律本身就解释了为什么那道特判是合理的——鸡蛋超过 log₂(n1) 之后就是纯浪费。顺带说一个能写进报告的小结论当 k 2 时答案是满足 m(m1)/2 ≥ n 的最小整数 m闭式解是 m ⌈(√(8n1) − 1) / 2⌉当 k 3 时答案是满足 m(m² 5)/6 ≥ n 的最小整数 m。这两个公式可以让你的报告看起来扎实很多。4.2 空间复杂度与 Python 的实际内存占用第三版只用了一个长度为 k 1 的列表空间复杂度 O(k)换算成实际内存在 k 被截断到 ⌈log₂(n1)⌉ 之后基本上就是几十个整数可以忽略不计。第二版要开 (k1) × (n1) 的二维表n 10⁴、k 100 时是 10⁶ 个单元Python 里每个 int 对象大约 28 字节加上 list 的指针数组实际占用在 40 MB 上下接近很多评测机的内存上限。这里有个经验Python 里存整数列表用array模块或者numpy能省不少内存但在这个题的规模下完全没必要直接换第三版更省事。如果实验报告里必须分析第二版的空间就老老实实写 O(k × n)然后补一句可用滚动数组优化到 O(k)这样既有分析又有优化意识。4.3 三版代码在同一台机器上的实测对比我在本地用 k 100、n 10000 这组数据跑了一遍Python 3.11普通笔记本结果如下版本理论复杂度实测耗时是否能过记忆化递归指数级带剪枝后接近 O(k × n²)直接 RecursionError调大递归深度后 30 秒以上没跑完不能二维递推O(k × n²)剪枝后实测快很多约 45 秒不能内层二分O(k × n × log n)约 22 秒勉强但体验很差一维滚动O(k × m)k 被截断到 14小于 1 毫秒完全没问题这个对比特别适合放报告里它直观地说明了换状态定义这一手比优化常数的收益高多少个数量级。从 45 秒到 0.001 秒靠的不是写得更紧凑而是换了个问题来算。5. 测试用例设计自造数据把代码逼到墙角5.1 必测的九组数据很多人交实验的时候只跑老师给的样例样例过了就以为万事大吉。我的习惯是自己设计一组能覆盖所有分支的数据下面这九组是我每次做这道题都会跑的编号kn期望输出这组数据在测什么1111最小非零规模211010单鸡蛋退化只能线性3263课本经典样例手算可验证4210014三角数公式验证53144组合数覆盖验证62100045中等规模性能71001000014鸡蛋过剩走特判分支8500零层楼边界9501000014大数据量正确性 性能双查第 3 组和第 5 组是能徒手验算的出错了立刻能定位。第 4 组我特别推荐k 2 时答案就是三角数m 13 覆盖 91 层m 14 覆盖 105 层所以 100 层的答案是 14这个推导过程可以直接写进实验报告当作算法正确性的验证。第 6 组 45 也是同理44 × 45 / 2 990 100045 × 46 / 2 1035 ≥ 1000。5.2 边界与极端值三类必须单独测的输入第一类是 n 0。这个输入下没有楼层需要确定答案应该是 0。如果你的代码在while dp[k] n之前先t 1就会返回 1差一位。我建议在函数最开头就把if n 0: return 0单独写出来。第二类是 k 0 且 n 0。数学上这是无解的没有鸡蛋永远测不出来但大多数题目保证 k ≥ 1所以可以不做处理但报告里最好提一句本算法假设 k ≥ 1显得你考虑过。第三类是 k 远大于 n。比如 k 10⁵、n 1这时特判分支会直接返回 1同时避免了内层循环跑十万次。这类数据是性能测试里的常客出题人特别喜欢用它来卡那些忘记截断 k 的写法。5.3 用暴力版当标程做对拍自己写的代码自己测很容易因为知道答案所以看不出错误。我用的办法是把 3.1 节的记忆化递归版当标程随机生成一批小规模数据k 在 1 到 5 之间n 在 0 到 200 之间两个程序同时跑逐个比对输出。只要有一组对不上就立刻把这组输入单独拎出来手推。import random for _ in range(500): k random.randint(1, 5) n random.randint(0, 200) a egg_drop_memo(k, n) b egg_drop_fast(k, n) if a ! b: print(不一致, k, n, a, b) break else: print(500 组随机数据全部通过)这十几行代码把我在边界上的所有问题都暴露出来了包括那个忘了处理 n 0的错误。做实验的时候多花五分钟写对拍比盯着屏幕猜哪里错了要高效得多。6. 踩坑记录那些让你反复提交错误的细节6.1 一维数组的遍历方向是这道题最大的陷阱第三版代码里那句for i in range(k, 0, -1)我第一遍写的时候写成了正序结果答案在小规模数据上碰巧对一到大 k 就偏小。原因拆开看转移式是 dp2[i][j] dp2[i][j-1] dp2[i-1][j-1] 1等号右边的两个量都属于上一轮也就是 j-1 次投掷的状态而数组 dp[i] 在更新前保留的正是上一轮的值。正序遍历时先算 dp[1]把 dp[1] 从上一轮改成了这一轮接着算 dp[2] 时用到的 dp[1] 已经是本轮的新值了等于把 dp2[i-1][j] 当成了 dp2[i-1][j-1] 用多算了一层结果偏大或者偏小的方向取决于具体数据非常隐蔽。倒序遍历时算 dp[i] 时 dp[i-1] 还没被本轮碰过用的就是干净的上一轮值。这个规律可以总结成一句话一维滚动数组的遍历方向永远让被依赖的那一项保持上一轮的值。如果依赖的是更小的下标就倒序如果依赖的是更大的下标就正序如果依赖的是自身比如完全背包就从依赖的下标开始正序。这个规则在 01 背包、完全背包、最长公共子序列的空间优化里全都通用。6.2 状态定义混用导致的隐性错误另一个常见的坑是在同一份代码里混用两套状态语义。比如前面用 dp[i][j] 表示i 枚鸡蛋确定 j 层的最少次数后面写转移时手一滑把 dp[i-1][x-1] 理解成了i-1 枚鸡蛋覆盖 x-1 层两种理解下的边界和增量都不一样代码不会报错但答案会系统性偏移。我的防护办法是把状态含义写在函数开头的注释里每次改代码前先读一遍那行注释。听起来很笨但确实有效。另外建议给两套实现的变量取不同的名字比如第一套用dp_min第二套用dp_cover从命名上就杜绝混用。6.3 递归版的两个隐蔽问题第一个是 Python 的默认递归深度只有 1000。记忆化递归版在 n 稍大时递归栈深度会随着 floors 减小而线性增长很容易触发 RecursionError。解决方式是sys.setrecursionlimit(200000)但要注意这个数字不能无脑开太大栈溢出会直接把进程干掉而不是抛异常。第二个是lru_cache的缓存键。如果参数里混进了列表或者可变对象缓存会直接失效程序会退化到指数复杂度。这道题的参数都是整数一般不会踩到但如果你把 floors 换成一个区间元组来表示任意区间有些变体题会这么干就要注意元组是不可变的缓存是安全的但缓存命中率会明显下降。6.4 常见问题速查表现象大概率原因排查动作小数据对大数据偏小一维数组正序遍历检查内层循环方向是否倒序答案比标准答案大 1n 0 时先自增了 t在函数开头单独返回 0大 k 时程序很慢没有截断 k加上 k ≥ m 时的提前返回报 RecursionError递归深度超限设置递归上限或改写成递推二维版本内存超限开了 (k1) × (n1) 的表换成滚动数组空间降到 O(k)递推版跑到一半超时内层 O(n) 枚举换第二套状态定义或加剪枝结果全部偏大边界 dp[i][1] 没初始化检查只有一层时的返回值C 提交答案离谱int 溢出把 dp 数组换成 long long这张表里最值得记住的是第一行和第二行它们覆盖了我遇到过的八成问题。7. 迁移训练鸡蛋掉落和 01 背包、车辆调度用的是同一套模板7.1 一维滚动数组的通用判断规则前面已经说过遍历方向的问题这里把它提炼成一条可复用的规则先写出二维转移式看清楚等号右边每个项是上一行同列、上一行前列还是本行前列。如果用到的是上一行同列和上一行前列比如 01 背包的 dp[j] max(dp[j], dp[j - w] v)那内层就要倒序遍历容量保证 dp[j - w] 还是上一行的值。如果用到的是本行前列比如完全背包的 dp[j] max(dp[j], dp[j - w] v)那就要正序遍历让 dp[j - w] 更新成本行的值。鸡蛋掉落的滚动是倒序遍历鸡蛋数因为依赖的 dp[i - 1] 是上一轮的。这几种情形看着五花八门其实判断标准只有一条看依赖项属于哪一行/哪一轮然后让遍历顺序保证它在该轮还没被覆盖。7.2 01 背包和鸡蛋掉落的对照把两个问题并排放能看到很多结构上的对应关系对比项鸡蛋掉落01 背包状态含义i 枚鸡蛋、j 层楼的最少次数前 i 件物品、容量 j 的最大价值二维转移dp[i][j] dp[i][j-1] dp[i-1][j-1] 1dp[i][j] max(dp[i-1][j], dp[i-1][j-w] v)一维优化dp[i] dp[i] dp[i-1] 1倒序 idp[j] max(dp[j], dp[j-w] v)倒序 j决策类型最优决策min-max最优决策max边界处理鸡蛋数或次数为 0 时返回 0前 0 件物品或容量为 0 时价值为 0常见变体求具体策略、求期望次数恰好装满、分组背包、多重背包写 01 背包的 Python 时最容易被忽略的是range(cap, weights[i] - 1, -1)里的终止位置——必须是weights[i] - 1因为j - weights[i]至少要等于 0写成了weights[i]就会漏掉恰好装满的那一种情况。这跟鸡蛋掉落里range(k, 0, -1)的终止位置必须是 0 是一个道理两边的下标边界都容易写错。def knapsack(weights, values, cap): dp [0] * (cap 1) for i in range(len(weights)): for j in range(cap, weights[i] - 1, -1): # 倒序且下界是 weights[i]-1 dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[cap]7.3 车辆调度类问题的建模切入点车辆动态规划这个词在算法课里通常指两类问题一类是路径规划类比如车辆从起点到终点每段路有油耗和速度限制求最小油耗或者最小时间另一类是车辆调度类比如有若干运输任务车辆有容量限制求最少用车数或者最小总成本。这两类问题的建模思路其实和鸡蛋掉落是一条线上的先问自己我有哪些资源是会被消耗的鸡蛋数、载重量、剩余油量我要覆盖或完成的目标是什么确定的楼层范围、所有任务然后定义状态为消耗了若干资源、完成了若干目标时的最优值。拿一个简化版的加油问题举例一辆车油箱容量 C从起点到终点依次经过 n 1 个站点第 i 站到第 i 1 站的距离是 d[i]第 i 站的油价是 p[i]。设 dp[i][j] 表示到达第 i 站时油箱还剩 j 升油的最小花费转移就是在第 i 站决定加多少油 k0 ≤ k ≤ C - j代价是 k × p[i]然后减掉这一段路的消耗。内层的 k 枚举同样是一个可以优化的点思路和鸡蛋掉落里的内层枚举优化完全一致——观察代价函数的单调性或凸性再决定用二分还是单调队列来压复杂度。把这三个问题摆在一起看你会发现动态规划的套路其实高度统一先把资源和目标两个维度定下来再写出这一步决策之后资源怎么变最后检查转移用的到底是上一轮还是本轮的表格。剩下的就是复杂度优化和边界处理这两件体力活了。最后分享一点我自己的体会。这道题我前后写废了四版代码真正卡住我的从来不是转移方程而是那句倒序遍历以及 n 0 的边界。后来我养成了一个习惯每写完一版 DP先不急着提交而是手推一个规模最小的用例把状态表在纸上画三行出来跟前一版对比。这个动作只要两分钟但能抓住绝大多数方向性错误。如果你也在做这个实验建议把 5.1 节那张表里的九组数据自己手推一遍再上机推完再去看代码很多坑其实根本不用踩。