尧图网站开发 
算法设计与分析这门课一讲到动态规划实验四的鸡蛋掉落问题基本都会成为讨论度最高的那道题。它的题面特别生活化——给你 K 个一模一样的鸡蛋一栋 N 层的楼存在一个临界楼层 F从 F 层及以上的楼层扔下去鸡蛋会碎从 F 层以下扔下去不会碎问在最坏情况下最少要扔多少次才能确定 F。但真正动手写的时候你会发现它不像 01 背包那样照着模板套就行状态怎么定义、内层那个 max 到底在 max 什么、为什么答案不是简单的二分这些点每一个都能卡住人。这道题值得单独拿出来讲是因为它一口气串起了动态规划里三个很核心的东西极小极大的转移结构、状态维度方向的重新选择、以及决策单调性优化。把这一道题吃透后面遇到分割数组、吃香蕉、称重找次品这类最坏情况下最优的题目思路基本可以直接搬。下面我按自己当时做实验的顺序从题意翻译、状态推导、复杂度优化一路讲到踩坑和测试数据构造代码以 Python 为主关键位置会说明为什么这么写。1. 实验四的题目到底在问什么把生活描述翻译成数学语言1.1 三个变量与一个最坏情况约束先把题面里的自然语言拆干净。这道题只有三个变量鸡蛋个数 K、楼层数 N、临界楼层 F。F 是一个未知的、固定不变的整数取值范围是 1 到 N也有教材把 F 定义成最高的安全楼层从而让 F 可以取 0两种定义在实现上差别不大但混用会让你在边界上多调半小时。每一次投掷你选一层楼把鸡蛋丢下去结果只有两种碎了这个蛋报废没碎这个蛋还能继续用。目标是在最坏情况下用最少的投掷次数把 F 唯一确定下来。最坏情况这四个字是整道题的灵魂。它不是求平均次数也不是求运气最好时的次数而是假设存在一个专门和你作对的答案序列专门挑让你多试几次的那个分支。你要给出的次数 m必须保证不管 F 是几你都能在 m 次以内确定它。很多同学第一次读题时把最坏情况理解成了鸡蛋一定会碎然后写出来的东西完全对不上样例这是最典型的读题失误。顺便记两个极端情况它们后面会反复用来验证代码。第一个极端是 K 1只有一个蛋碎了就没了所以你没有任何容错空间只能从 1 楼开始一层一层往上试答案就是 N。第二个极端是 K 足够大蛋多到用不完那就直接二分答案是 ⌈log₂(N1)⌉。这两个值是天然的上下界锚点你的程序如果在这两组输入上跑不对就不用去看大数据了。1.2 为什么第一直觉二分、均分都会翻车绝大多数人看到确认一个临界值的第一反应是二分我当初也是。2 个蛋、100 层楼二分第一次扔 50 层。如果碎了你只剩 1 个蛋还得从 1 楼一路线性扫到 49 楼最坏情况是 1 49 50 次。正确答案是 14 次差了 3 倍多。二分的失败原因很直白二分是建立在每次尝试都能排除一半的前提上的而这个前提依赖于你有无限次试错机会蛋一碎你的试错预算就少了一份。第二个直觉是均分楼层。把 100 层分成 10 段每段 10 层先在 10、20、30 这些位置扔找到所在的段之后再在段内线性扫。最坏情况是 10找段 10段内 20 次比 50 好但依然不是最优。均分的问题是它把工作量平均分配在了找段和段内两个阶段而实际上这两个阶段消耗的鸡蛋数量不同容错能力也不同所以平均分配并不是最优策略。真正的最优策略是让碎了和没碎两种结果剩下的工作量尽量相等而且要考虑到碎一次就少一个蛋。具体到 2 蛋 100 层第一次应该在 14 层扔如果没碎第二次在 14 13 27 层扔再没碎就是 27 12 39 层每次往上加的楼层数递减 1。这样 14 次总共能覆盖 14 13 12 … 1 105 层刚好够 100 层。这个递减增量的规律不是拍脑袋来的它和后面要讲的组合数公式是同一个东西的两种表达。1.3 把最少几次改写成m 次能不能覆盖做实验报告的时候我建议把问题在草稿纸上做一次形式转换不去直接求最少几次而是问如果只给我 m 次投掷机会我最多能确定多少层楼。定义一个函数can(k, m)表示 k 个蛋、m 次机会能覆盖的楼层数那么最终答案就是满足can(K, m) N的最小 m。这个改写看起来只是换了个说法价值却很大。第一can关于 m 是单调不减的你要么直接递推要么在外层对 m 做二分两种做法都成立。第二最优化形式的转移方程带 min 带 max容易写错边界判定形式的方程只有一个加法写起来错不了。第三判定形式天然把复杂度从楼层维平方降到了次数维线性这是第三章那个 O(K·N) 解法的思想源头。提示题目里的 N 和 m 是两个不同的量纲。N 是楼层数m 是投掷次数虽然它们的最大值都是 NK 1 时但千万不要在推导时把两者当成一回事这是后来我给别人讲题时发现的最常见的思维混乱点。2. 状态怎么定义dp[k][n] 的推导与边界处理2.1 从在某一层扔一次拆出两个子问题正向 DP 的状态定义是dp[k][n]表示有 k 个鸡蛋、面对 n 层楼、在最坏情况下确定临界楼层所需的最少投掷次数。注意这里说的是面对 n 层楼也就是这 n 层里必然藏着答案可能是任意一层。现在考虑第一次投掷。我们选择在第 i 层扔i 的取值范围是 1 到 n。扔完之后只有两种结果。如果鸡蛋碎了说明临界楼层在 i 层以下或者就是 i 层取决于 F 的定义剩下的搜索区间是 i - 1 层而鸡蛋只剩 k - 1 个于是子问题变成dp[k-1][i-1]。如果鸡蛋没碎说明临界楼层在 i 层以上剩下的搜索区间是 n - i 层鸡蛋个数不变还是 k 个子问题变成dp[k][n-i]。这里有一个特别容易搞错的细节碎了的子问题里区间大小是i - 1而不是i。因为第 i 层本身已经被这一次投掷测试过了它的结果是确定的不需要再搜索。同理没碎的时候区间是n - i而不是n - i 1。我见过不少人把这两处写成i和n - i 1结果小数据上看着对大数据上永远差 1非常难查。2.2 为什么转移方程里是 max 套 min写出完整的转移方程dp[k][n] min over i in [1, n] of { 1 max( dp[k-1][i-1], dp[k][n-i] ) }内层是 max外层是 min这个结构叫极小极大minimax。理解它的关键是分清哪一部分是你能控制的哪一部分是你不能控制的。外层用 min是因为第 i 层的选择权在你手里。你是策略的制定者你可以决定第一次在哪层扔所以你当然要挑那个让最坏结果最小的 i。内层用 max是因为鸡蛋碎不碎这件事不由你决定我们讨论的又是最坏情况所以要取两种结果里更耗时的那个。一句话总结min 是我们的选择权max 是最坏情况的假设。还有一个高频错误是把内层写成加法也就是1 dp[k-1][i-1] dp[k][n-i]。这么写的同学脑子里想的是碎了我走一遍下面没碎我再走一遍上面但这两种情况是互斥的真实执行时只会走其中一条路径所以要用 max 取最坏的那条而不是把两条加起来。加法会得到一个明显偏大的答案2 蛋 100 层会跑出 20 以上看到这种结果基本就能定位到这里了。2.3 边界条件dp[0][n] 的取值决定了你会不会写错边界条件是这道题最大的坑没有之一。先把正确的边界列出来dp[k][0] 0零层楼不需要扔直接确定。dp[1][n] n一个蛋只能线性扫。dp[0][n] INFn 0零个蛋面对非空楼层无论扔多少次都确定不了必须是无穷大。dp[0][0] 0注意这一条和上一条不冲突零层楼配零个蛋是合法的终止状态。第三和第四条是整个实现里最微妙的地方。如果图省事把dp[0][*]全部初始化为 0你的程序会给出偏小的答案因为max(dp[0][i-1], ...)会取到 0等价于宣称一个蛋都没有也能确定 i - 1 层楼这显然不成立。更隐蔽的是dp[0][0]如果也被设成 INF那dp[1][n]的递推会整个崩掉因为 K 1 时子问题里必然会用到dp[0][0]。我在第一次写的时候就是全表初始化成 INF然后 1 个蛋的测试用例全挂了。实际实现时不用真的用浮点无穷用一个安全的整数上界就够了比如N 1因为任何合法答案都不会超过 N。用整数还有个好处不会出现浮点比较的边界问题也不会在max里引入奇怪的 NaN。注意dp[k][n]有两个单调性质可以用来交叉验证你的程序——关于 k 单调不增蛋多了不会更差关于 n 单调不减楼层多了不会更好。如果你打印出来的 DP 表违反了这两条即使答案碰巧对了也说明转移写错了。3. 换维度求解dp[k][m] 最多能确定多少层楼3.1 逆向定义带来的复杂度降维正向 DP 的时间复杂度是 O(K · N²)因为外层两层循环内层还有一个大小为 n 的枚举。K 10、N 10000 时就是 5 亿次内层操作Python 里基本没法跑。解决这个问题最漂亮的办法不是优化那个内层循环而是换一个状态定义。新定义dp[k][m]表示 k 个鸡蛋、允许投掷 m 次最多能保证确定多少层楼。这个定义把次数从答案变成了状态把楼层数从状态变成了答案两个维度直接对调。推导过程很简洁。第一次投掷之后如果鸡蛋碎了我们还有 m - 1 次机会和 k - 1 个鸡蛋这部分能覆盖dp[k-1][m-1]层全部放在下面。如果鸡蛋没碎我们还有 m - 1 次机会和 k 个鸡蛋这部分能覆盖dp[k][m-1]层全部放在上面。最后再加上被投掷的那一层本身。于是dp[k][m] dp[k-1][m-1] dp[k][m-1] 1边界是dp[k][0] 0和dp[0][m] 0零个蛋一次能覆盖的楼层数当然是 0这里用 0 而不是 INF因为定义变成了能覆盖多少而不是需要几次性质完全反过来了这也是很多人在这儿写错的原因。最终答案是满足dp[K][m] N的最小 m。时间复杂度 O(K · M)而 M 最坏等于 N所以是 O(K · N)空间也是 O(K · N)。相比正向的 O(K · N²)在 N 10000、K 10 这个量级上差了整整四个数量级实测差距是跑几分钟和跑几毫秒的区别。3.2 组合数视角答案等价于找最小的 m 使 ΣC(m,i) ≥ N把上面的递推式展开你会发现一个很妙的结论dp[k][m] C(m,1) C(m,2) ... C(m,k)其中约定 i m 时 C(m, i) 0。验证一下k 1 时只剩 C(m,1) m和一个蛋线性扫 m 层完全吻合k 2、m 14 时是 C(14,1) C(14,2) 14 91 105正好对上前面说的 2 蛋 100 层需要 14 次k ≥ m 时求和等于 2^m - 1也就是蛋足够多等价于二分因为一下就能从 2^m - 1 层里用二分定位。这个公式的好处是能直接手算考试里特别管用。它还有一层直观解释可以的组合数C(m, i)表示的是在 m 次投掷里恰好碎掉 i 个蛋这种情况所能区分出的楼层数量所有可能的碎裂次数加起来就是总覆盖能力。换个说法dp[k][m]就是杨辉三角第 m 行的前 k 项之和这和每次投掷把问题分成两叉的树形结构是同一件事。有了这个公式两个极端情况的答案可以直接写出来不用跑程序。K 1 时答案是 NK ≥ ⌈log₂(N1)⌉ 时答案是 ⌈log₂(N1)⌉。后面构造测试数据的时候这两条就是免费的标杆答案。3.3 滚动数组实现与答案定位的细节二维版本写起来最直观但既然dp[k][m]只依赖第 m - 1 次的结果完全可以压成一维def super_egg_drop_1d(K, N): if N 0: return 0 K min(K, N) # 蛋多到超过楼层数没有意义截断省内存 dp [0] * (K 1) # dp[k] 表示 k 个蛋、当前 m 次能覆盖的楼层数 m 0 while dp[K] N: m 1 prev 0 # 代表 dp[k-1][m-1]k1 时它是 dp[0][m-1] 0 for k in range(1, K 1): old dp[k] # 旧值就是 dp[k][m-1] dp[k] old prev 1 prev old # 给下一个 k 用对应 dp[k][m-1] return m这段代码有几个地方值得停下来看。第一K min(K, N)是安全的截断因为 K 1 时答案最多是 N蛋的个数超过楼层数纯属浪费内存更紧的截断是min(K, ceil(log2(N1)))因为超过这个数答案就固定是二分的次数了。第二内层循环里prev的更新顺序很关键必须先把旧值存进old再赋给prev否则你在计算dp[k]的时候已经把dp[k-1]覆盖掉了结果会偏大。第三循环的上界是 N因为 K 1 时答案就是 N数组必须开到N 1不然会越界。二维版本更适合写实验报告因为表结构一眼就能看出状态之间的关系def super_egg_drop_2d(K, N): if N 0: return 0 K min(K, N) dp [[0] * (N 1) for _ in range(K 1)] # dp[k][m] m 0 while dp[K][m] N: m 1 for k in range(1, K 1): dp[k][m] dp[k][m - 1] dp[k - 1][m - 1] 1 return m写这段代码时要注意循环顺序外层必须是 m 递增内层必须是 k 递增两个顺序都不能换。因为dp[k][m]同时依赖同一行的前一列和上一行的前一列两个方向都必须是从小到大。4. 两个把 O(KN²) 压下去的优化二分查找与决策点单调4.1 固定 k 时 f(i) 是 V 形函数二分的前提如果你坚持要写正向 DP很多时候实验报告要求给出问题的最优子结构并实现那就必须在那个内层枚举上做文章。固定 k 和 n定义f(i) max( dp[k-1][i-1], dp[k][n-i] )注意 i 从 1 变到 n 的过程中两个分支的变化方向是相反的A(i) dp[k-1][i-1]随着 i 增大而单调不减因为楼层越多需要的次数越多B(i) dp[k][n-i]随着 i 增大而单调不增因为剩下的楼层越来越少。一个单调不减的函数和一个单调不增的函数取 max得到的必然是先降后升的 V 形函数严格说是非增段接非减段。这就意味着f(i)一定有唯一的一段极小值区间而我们要找的最低点就在A(i)和B(i)曲线交叉的位置附近。这个 V 形性质是二分查找能用的理论依据不是凭感觉二分的。如果你没想清楚这一点就去写二分很容易写出一个看起来能过样例、实际在大数据上错得离谱的版本。4.2 二分实现以及最优解在 lo 或 lo-1的处理我们要找的是使得A(i) B(i)成立的最小 i把这个位置记作 lo。由于函数是 V 形的最优解一定在 lo 或者 lo - 1 这两个候选里两个都算一遍取小值就万无一失了def super_egg_drop_binary(K, N): if N 0: return 0 K min(K, N) prev [0] * (N 1) # dp[k-1][*] for n in range(1, N 1): prev[n] n # k 1 的基准行 if K 1: return N for k in range(2, K 1): cur [0] * (N 1) # dp[k][*] for n in range(1, N 1): lo, hi 1, n while lo hi: mid (lo hi) // 2 if prev[mid - 1] cur[n - mid]: lo mid 1 else: hi mid best 1 max(prev[lo - 1], cur[n - lo]) if lo 1: # 平台期可能让最优解落在左边一格 best min(best, 1 max(prev[lo - 2], cur[n - lo 1])) cur[n] best prev cur return prev[N]这段代码的时间复杂度是 O(K · N · log N)空间用滚动数组压到了 O(N)。它比第 3 章的 O(K · N) 慢一个 log但优点是逻辑上完全沿着原始转移方程走推导过程和实验报告里的公式一一对应答辩的时候好解释。提示二分写完之后一定要拿只有 2 个蛋的小数据打表看一遍cur数组。2 蛋时cur[n]的增长是阶梯状的比如 1, 2, 2, 3, 3, 3, 3, 4, 4, …如果打出来是平滑的线性增长说明二分的比较方向反了。4.3 决策点单调性 爬坡理论 O(KN) 的做法还有一个更进一步的优化思路是利用决策点单调这个性质对于固定的 k最优的第一次投掷位置opt[k][n]随着 n 增大是单调不减的。这个性质可以用四边形不等式证明实验报告里如果不想展开证明至少也要用程序打印几行opt数组验证一下看到它确实是单调的再往下写。把它和 4.1 的 V 形性质结合起来就得到一个很干净的算法既然函数是 V 形的而谷底位置又随着 n 往右移动那我就不用从头枚举直接从上一层的决策点位置开始往右走一旦发现函数值开始上升就停下。def super_egg_drop_mono(K, N): if N 0: return 0 K min(K, N) dp [[0] * (N 1) for _ in range(K 1)] for n in range(1, N 1): dp[1][n] n for k in range(2, K 1): opt 1 for n in range(1, N 1): i min(opt, n) # 决策点单调从上一层的谷底开始 best 1 max(dp[k - 1][i - 1], dp[k][n - i]) best_i i while i n: # 沿谷底向右爬直到函数值不再下降 cand 1 max(dp[k - 1][i], dp[k][n - i - 1]) if cand best: best cand i 1 best_i i else: break dp[k][n] best opt best_i return dp[K][N]复杂度分析很有意思。对固定的 kn 从 1 到 N 的过程中决策点opt[k][n]从 1 单调走到最多 N每次的总步数是相邻两层决策点之差加一累加起来就是 O(N)。所以整个算法是 O(K · N) 的和第 3 章的逆向 DP 同阶。但两者各有各的好逆向 DP 空间可以压到 O(N) 而且代码短但需要你理解覆盖楼层数这个反直觉的定义决策单调版用的是最原始的正向状态定义推导过程直接对应实验报告里的公式同时又能达到线性复杂度。如果你的实验报告要求必须基于原始状态定义给出优化那就用这一版。5. 我在实现和调试中踩过的坑5.1 dp[0][n] 0 导致答案偏小的隐蔽 bug这个坑我在前面提过一次但值得单独展开因为它的隐蔽程度真的很高。现象是这样的我写完正向 DP 之后拿 2 蛋 100 层测试程序输出 10拿 3 蛋 100 层测试输出 8。这两个数字都在看起来合理的范围内不像溢出或者崩栈那么扎眼所以很容易被误认为算法没问题可能是我记错了标准答案。排查的过程是这样的。第一步我打印了完整的 DP 表重点看第 0 行。发现dp[0][*]全是 0因为 Python 里[[0]*(n1) ...]初始化之后就长这样。第二步我手动代入 n 1、k 2 算了一遍dp[2][1] 1 max(dp[1][0], dp[2][0]) 1 0 1这个是对的。第三步我算 n 2、k 2i 1时max(dp[1][0], dp[2][1]) max(0, 1) 1i 2时max(dp[1][1], dp[2][0]) max(1, 0) 1取 min 加 1 得 2也是对的。第四步我算 k 3、n 5 的时候i 1分支里出现了max(dp[2][0], dp[3][4])没问题但i 3分支里出现了max(dp[2][2], dp[3][2])还是没问题。真正出问题的是当 k 继续增大、内层用到dp[k-1][i-1]且i - 1恰好为 0 时——不对那时候dp[k-1][0]本身是 0是正确的。我把这个问题重新想了一遍才定位到真正的原因错误不在dp[0][0]而在当 k 1 且 n 0 时如果程序在内层循环里尝试走碎蛋分支。因为dp[1][n]我单独赋值成了 n所以正向 DP 的 k 1 那层是没问题的问题出在我为了代码统一把 k 1 也放进了循环里让程序自己去算dp[1][n]而此时dp[0][i-1]全是 0max就会取到另一边的值导致dp[1][n]被算成了一个很小的数然后这个错误值一路传播到所有更大的 k。修复办法有两条选哪条都行。一是把 k 1 那层单独初始化循环从 k 2 开始这也是我最后采用的做法。二是把dp[0][n]n 0设成一个足够大的整数比如N 1让max在组合蛋数为 0 的时候必然取到它从而把这条路堵死。两条路都通向正确的答案但绝对不能两条都不做。5.2 Python 里递归记忆化和三层循环的性能陷阱很多同学写 DP 喜欢用递归加functools.lru_cache因为转移方程照抄下来就行不用想循环顺序。在这道题上这个习惯会带来两个麻烦。第一个是递归深度。dp[k][n]在展开过程中会调用dp[k][n-1]、dp[k][n-2]等等虽然用了记忆化之后实际计算量是 O(K · N²)但递归调用链条的长度在最坏情况下会接近 N。当 N 10000 时Python 默认的递归上限 1000 会直接抛RecursionError。你可以手动调sys.setrecursionlimit但这只是把问题往后推深度上万之后 C 栈本身也有风险。第二个是缓存字典的开销。lru_cache每次调用都要做一次哈希查找和参数打包常数开销比数组下标访问大得多。同一组数据数组版本可能在 0.5 秒内跑完带装饰器的递归版本要跑十几秒。三层循环的问题更直接内层枚举是 n 次中间层和外面层加起来是 K · N总操作数是 O(K · N²)。K 10、N 10000 时是 5 亿次循环Python 里每次循环还要做函数调用级别的字典索引实测是分钟级的量。这种情况下最实际的做法是小数据N ≤ 200用朴素三层循环保证正确性大数据直接换第 3 章或第 4 章的优化版本。如果非要在 Python 里优化朴素版有两个立竿见影的小技巧。一是把dp[k-1]和dp[k]提前绑定到局部变量减少一层下标索引实测能快 20% 到 30%up dp[k - 1] cur dp[k] for n in range(1, N 1): best N 1 for i in range(1, n 1): v up[i - 1] if up[i - 1] cur[n - i] else cur[n - i] if v 1 best: best v 1 cur[n] best二是遇到 K 很大时提前截断因为K ceil(log2(N1))之后答案就固定了可以直接返回不用真的去算 K 层循环。这个截断在 LeetCode 那类 K 达到上百的测试里特别有用。5.3 边界与特殊输入的检查清单把边界情况整理成一张表写完代码之后照着过一遍能省掉大量调试时间。我把这几组数据的标准答案也一并列出来了其中括号里标注的是常见错误输出方便你对照排查。输入标准答案常见错误输出与原因N 0任意 K0输出 1把零层楼当成需要扔一次K 1N 100100输出 7误用了二分的结论K 2N 11输出 0忘记加投掷本身的那一次K 2N 22输出 1dp[0][n] 0的传播错误K 3N 144输出 5内层用了加法而不是 maxK 2N 10014输出 10dp[0][n] 0导致偏小K 100N 1000014栈溢出或超时用了朴素递归最后一行还能顺便验证蛋足够多就等价于二分这个结论二分的次数是 ⌈log₂(10001)⌉ 14答案是 14两者一致。这类两个不同思路得到同一个答案的交叉验证比单纯跑样例有效得多。6. 测试数据怎么造、答案怎么验6.1 小规模暴力对拍自己写的优化版本最怕的就是看起来对所以一定要准备一个逻辑绝对正确的暴力版本用来对拍。在这个问题上暴力版本最简单直接用正向转移方程写记忆化递归不做任何优化代码短到不可能写错from functools import lru_cache def brute(K, N): INF N 1 lru_cache(maxsizeNone) def dp(k, n): if n 0: return 0 if k 0: return INF if k 1: return n return 1 min(max(dp(k - 1, i - 1), dp(k, n - i)) for i in range(1, n 1)) return dp(K, N)对拍脚本的框架也很简单随机生成 K 在 1 到 5 之间、N 在 1 到 30 之间的数据跑 1000 组把暴力版和你写的优化版结果逐个比较一旦不一致就立刻打印参数退出。1000 组小数据在 Python 里几秒钟就能跑完但能覆盖到绝大多数边界分支。对拍的时候还有一个小技巧不要只比较最终答案也把 DP 表整体比较一遍。最终答案相同但表不同的情况虽然罕见但一旦出现就说明某个位置的转移有偏差而这种偏差很可能在你换一组更大的数据时就暴露出来。把表比较加上相当于把检查粒度从一个点提升到整张表。6.2 几组能手算出来的标杆数据除了对拍手算几组数据作为锚点也很有必要因为它能验证你的理解而不只是验证你的程序。这里挑三组我当年写在实验报告里的推导过程。第一组K 2、N 100答案是 14。推导方式用递减增量假设第一次在 x 层扔如果碎了还剩 x - 1 层需要 1 个蛋线性扫最坏是 1 (x - 1) x 次如果没碎第二次要往上走 x - 1 层到 2x - 1 层这样每次的增量递减 1总的覆盖能力是 x (x - 1) … 1 x(x1)/2。要让这个值不小于 100解 x(x1)/2 ≥ 100 得到 x 1414 × 15 / 2 10513 × 14 / 2 91 不够所以答案是 14。第二组K 3、N 14答案是 4。用组合数公式算dp[3][4] C(4,1) C(4,2) C(4,3) 4 6 4 14刚好等于 14而 dp[3][3] 3 3 1 7 14所以最小的 m 就是 4。第三组K 100、N 10000答案是 14。因为蛋多到用不完等价于二分⌈log₂(10001)⌉ 14。用组合数验证dp[100][14] 2^14 - 1 16383 ≥ 10000而 dp[100][13] 2^13 - 1 8191 10000所以是 14。这三组数据分别覆盖了蛋少、蛋中等、蛋多到饱和三种场景如果程序在这三组上都对基本上可以认为实现是可靠的。6.3 复杂度与实测对比表把各个版本的复杂度整理在一起写实验报告的复杂度分析章节时直接抄这张表就行。最后一列是我在笔记本上跑 K 10、N 10000 时的实际感受标注的是数量级而不是精确毫秒因为不同机器差异很大但量级关系是稳定的。实现方式时间复杂度空间复杂度实测感受朴素正向 DP三层循环O(K · N²)O(K · N)分钟级基本不可接受朴素正向 DP 滚动数组O(K · N²)O(N)内存好了时间没救二分优化正向 DPO(K · N · log N)O(N)秒级能接受决策点单调正向 DPO(K · N)O(N)毫秒级推荐逆向覆盖楼层 DPO(K · N)O(N)毫秒级代码最短组合数公式 逐 m 递推O(K · N)O(K)毫秒级适合手算验证有一个细节值得注意反向 DP 的循环次数其实是 K × M其中 M 是答案而不是 K × N。当 K 很小的时候M 可能远小于 N比如 2 蛋 10000 层的答案只有 141因为 141 × 142 / 2 10011 ≥ 10000所以它在实际运行中常常比表格里写的还要快。7. 从鸡蛋掉落往外推这类极小极大型 DP 的通用套路7.1 一眼认出极小极大型 DP 的三个特征做完整道题之后我发现这类题目其实有一套很明显的识别特征抓住这三点基本就能判断该用什么样的状态定义。第一个特征是保证和最坏情况这类词。只要题面里出现无论……都能确定、最坏情况下最少、一定能找到就说明存在一个对手模型转移方程里必然有 max 取最坏分支。第二个特征是消耗型资源。鸡蛋是消耗品碎了就少一个这种操作会损耗资源的设定往往会让状态里多一个维度比如鸡蛋个数、剩余次数、剩余容量。很多同学看到这种题第一反应是贪心但资源消耗会导致局部最优解不成立必须用 DP 或者二分答案加判定。第三个特征是决策点具有单调性。这类问题的最优决策位置通常随着问题规模单调移动这既是优化复杂度的突破口也是验证实现是否正确的信号。如果你打印出来的决策点数组是来回跳的八成是转移方程写错了。顺着这套特征去看能归到同一类的题目还有不少分割数组使最大子数组和最小LeetCode 410、爱吃香蕉的珂珂LeetCode 875、在 D 天内送达包裹的能力LeetCode 1011它们都是答案二分加可行性判定的结构判定函数里藏着 max 和 min 的组合。把它们放在一起练一遍动态规划这一章的题感会明显不一样。7.2 写实验报告时容易被扣分的地方最后说说实验报告。这道题的实验报告如果只是贴一坨能跑的代码分数通常不会太高因为老师要看的是你对问题的分析过程。我的经验是把下面几件事写清楚比代码多写两百行都管用。第一状态定义必须写清楚每个下标的含义包括它的取值范围和物理意义。dp[k][n]里的 k 是剩余的鸡蛋数而不是已经碎掉的鸡蛋数这种细节一定要在报告里说死否则后面所有的推导都会被认为是蒙对的。第二转移方程要配上文字说明尤其是max和min各自的现实含义。很多报告只写公式不写解释阅卷的人没法判断你是理解了还是抄的。第三边界条件要单独列一个表把dp[k][0]、dp[0][n]、dp[0][0]三种情况都写出来并说明理由。我在前面说过这几个地方年年有人写错。第四测试数据要给出输入—输出—验证方式三列最好附上和对拍脚本的对比结果。手算推导出来的那三组标杆数据2 蛋 100 层、3 蛋 14 层、100 蛋 10000 层一定要写进去它们能直接证明你的程序不是碰巧过的。第五复杂度分析要分别给出时间和空间并且说明为什么两个维度的上界分别是 K 和 N。如果做了优化要把优化前后的复杂度放在一起对比解释优化利用了哪条性质。我个人在这道题上最大的收获其实不是学会了某个具体的优化技巧而是第一次真切体会到状态定义的方向可以换这件事。同一道题正向定义是 O(K · N²)把次数和楼层数对调一下变成 O(K · N)代码量还更少。后来再遇到卡住的 DP 题我都会先问自己一句是不是把某个维度定义反了这个习惯比记住任何一个具体方程都值钱。 
算法设计与分析这门课一讲到动态规划实验四的鸡蛋掉落问题基本都会成为讨论度最高的那道题。它的题面特别生活化——给你 K 个一模一样的鸡蛋一栋 N 层的楼存在一个临界楼层 F从 F 层及以上的楼层扔下去鸡蛋会碎从 F 层以下扔下去不会碎问在最坏情况下最少要扔多少次才能确定 F。但真正动手写的时候你会发现它不像 01 背包那样照着模板套就行状态怎么定义、内层那个 max 到底在 max 什么、为什么答案不是简单的二分这些点每一个都能卡住人。这道题值得单独拿出来讲是因为它一口气串起了动态规划里三个很核心的东西极小极大的转移结构、状态维度方向的重新选择、以及决策单调性优化。把这一道题吃透后面遇到分割数组、吃香蕉、称重找次品这类最坏情况下最优的题目思路基本可以直接搬。下面我按自己当时做实验的顺序从题意翻译、状态推导、复杂度优化一路讲到踩坑和测试数据构造代码以 Python 为主关键位置会说明为什么这么写。1. 实验四的题目到底在问什么把生活描述翻译成数学语言1.1 三个变量与一个最坏情况约束先把题面里的自然语言拆干净。这道题只有三个变量鸡蛋个数 K、楼层数 N、临界楼层 F。F 是一个未知的、固定不变的整数取值范围是 1 到 N也有教材把 F 定义成最高的安全楼层从而让 F 可以取 0两种定义在实现上差别不大但混用会让你在边界上多调半小时。每一次投掷你选一层楼把鸡蛋丢下去结果只有两种碎了这个蛋报废没碎这个蛋还能继续用。目标是在最坏情况下用最少的投掷次数把 F 唯一确定下来。最坏情况这四个字是整道题的灵魂。它不是求平均次数也不是求运气最好时的次数而是假设存在一个专门和你作对的答案序列专门挑让你多试几次的那个分支。你要给出的次数 m必须保证不管 F 是几你都能在 m 次以内确定它。很多同学第一次读题时把最坏情况理解成了鸡蛋一定会碎然后写出来的东西完全对不上样例这是最典型的读题失误。顺便记两个极端情况它们后面会反复用来验证代码。第一个极端是 K 1只有一个蛋碎了就没了所以你没有任何容错空间只能从 1 楼开始一层一层往上试答案就是 N。第二个极端是 K 足够大蛋多到用不完那就直接二分答案是 ⌈log₂(N1)⌉。这两个值是天然的上下界锚点你的程序如果在这两组输入上跑不对就不用去看大数据了。1.2 为什么第一直觉二分、均分都会翻车绝大多数人看到确认一个临界值的第一反应是二分我当初也是。2 个蛋、100 层楼二分第一次扔 50 层。如果碎了你只剩 1 个蛋还得从 1 楼一路线性扫到 49 楼最坏情况是 1 49 50 次。正确答案是 14 次差了 3 倍多。二分的失败原因很直白二分是建立在每次尝试都能排除一半的前提上的而这个前提依赖于你有无限次试错机会蛋一碎你的试错预算就少了一份。第二个直觉是均分楼层。把 100 层分成 10 段每段 10 层先在 10、20、30 这些位置扔找到所在的段之后再在段内线性扫。最坏情况是 10找段 10段内 20 次比 50 好但依然不是最优。均分的问题是它把工作量平均分配在了找段和段内两个阶段而实际上这两个阶段消耗的鸡蛋数量不同容错能力也不同所以平均分配并不是最优策略。真正的最优策略是让碎了和没碎两种结果剩下的工作量尽量相等而且要考虑到碎一次就少一个蛋。具体到 2 蛋 100 层第一次应该在 14 层扔如果没碎第二次在 14 13 27 层扔再没碎就是 27 12 39 层每次往上加的楼层数递减 1。这样 14 次总共能覆盖 14 13 12 … 1 105 层刚好够 100 层。这个递减增量的规律不是拍脑袋来的它和后面要讲的组合数公式是同一个东西的两种表达。1.3 把最少几次改写成m 次能不能覆盖做实验报告的时候我建议把问题在草稿纸上做一次形式转换不去直接求最少几次而是问如果只给我 m 次投掷机会我最多能确定多少层楼。定义一个函数can(k, m)表示 k 个蛋、m 次机会能覆盖的楼层数那么最终答案就是满足can(K, m) N的最小 m。这个改写看起来只是换了个说法价值却很大。第一can关于 m 是单调不减的你要么直接递推要么在外层对 m 做二分两种做法都成立。第二最优化形式的转移方程带 min 带 max容易写错边界判定形式的方程只有一个加法写起来错不了。第三判定形式天然把复杂度从楼层维平方降到了次数维线性这是第三章那个 O(K·N) 解法的思想源头。提示题目里的 N 和 m 是两个不同的量纲。N 是楼层数m 是投掷次数虽然它们的最大值都是 NK 1 时但千万不要在推导时把两者当成一回事这是后来我给别人讲题时发现的最常见的思维混乱点。2. 状态怎么定义dp[k][n] 的推导与边界处理2.1 从在某一层扔一次拆出两个子问题正向 DP 的状态定义是dp[k][n]表示有 k 个鸡蛋、面对 n 层楼、在最坏情况下确定临界楼层所需的最少投掷次数。注意这里说的是面对 n 层楼也就是这 n 层里必然藏着答案可能是任意一层。现在考虑第一次投掷。我们选择在第 i 层扔i 的取值范围是 1 到 n。扔完之后只有两种结果。如果鸡蛋碎了说明临界楼层在 i 层以下或者就是 i 层取决于 F 的定义剩下的搜索区间是 i - 1 层而鸡蛋只剩 k - 1 个于是子问题变成dp[k-1][i-1]。如果鸡蛋没碎说明临界楼层在 i 层以上剩下的搜索区间是 n - i 层鸡蛋个数不变还是 k 个子问题变成dp[k][n-i]。这里有一个特别容易搞错的细节碎了的子问题里区间大小是i - 1而不是i。因为第 i 层本身已经被这一次投掷测试过了它的结果是确定的不需要再搜索。同理没碎的时候区间是n - i而不是n - i 1。我见过不少人把这两处写成i和n - i 1结果小数据上看着对大数据上永远差 1非常难查。2.2 为什么转移方程里是 max 套 min写出完整的转移方程dp[k][n] min over i in [1, n] of { 1 max( dp[k-1][i-1], dp[k][n-i] ) }内层是 max外层是 min这个结构叫极小极大minimax。理解它的关键是分清哪一部分是你能控制的哪一部分是你不能控制的。外层用 min是因为第 i 层的选择权在你手里。你是策略的制定者你可以决定第一次在哪层扔所以你当然要挑那个让最坏结果最小的 i。内层用 max是因为鸡蛋碎不碎这件事不由你决定我们讨论的又是最坏情况所以要取两种结果里更耗时的那个。一句话总结min 是我们的选择权max 是最坏情况的假设。还有一个高频错误是把内层写成加法也就是1 dp[k-1][i-1] dp[k][n-i]。这么写的同学脑子里想的是碎了我走一遍下面没碎我再走一遍上面但这两种情况是互斥的真实执行时只会走其中一条路径所以要用 max 取最坏的那条而不是把两条加起来。加法会得到一个明显偏大的答案2 蛋 100 层会跑出 20 以上看到这种结果基本就能定位到这里了。2.3 边界条件dp[0][n] 的取值决定了你会不会写错边界条件是这道题最大的坑没有之一。先把正确的边界列出来dp[k][0] 0零层楼不需要扔直接确定。dp[1][n] n一个蛋只能线性扫。dp[0][n] INFn 0零个蛋面对非空楼层无论扔多少次都确定不了必须是无穷大。dp[0][0] 0注意这一条和上一条不冲突零层楼配零个蛋是合法的终止状态。第三和第四条是整个实现里最微妙的地方。如果图省事把dp[0][*]全部初始化为 0你的程序会给出偏小的答案因为max(dp[0][i-1], ...)会取到 0等价于宣称一个蛋都没有也能确定 i - 1 层楼这显然不成立。更隐蔽的是dp[0][0]如果也被设成 INF那dp[1][n]的递推会整个崩掉因为 K 1 时子问题里必然会用到dp[0][0]。我在第一次写的时候就是全表初始化成 INF然后 1 个蛋的测试用例全挂了。实际实现时不用真的用浮点无穷用一个安全的整数上界就够了比如N 1因为任何合法答案都不会超过 N。用整数还有个好处不会出现浮点比较的边界问题也不会在max里引入奇怪的 NaN。注意dp[k][n]有两个单调性质可以用来交叉验证你的程序——关于 k 单调不增蛋多了不会更差关于 n 单调不减楼层多了不会更好。如果你打印出来的 DP 表违反了这两条即使答案碰巧对了也说明转移写错了。3. 换维度求解dp[k][m] 最多能确定多少层楼3.1 逆向定义带来的复杂度降维正向 DP 的时间复杂度是 O(K · N²)因为外层两层循环内层还有一个大小为 n 的枚举。K 10、N 10000 时就是 5 亿次内层操作Python 里基本没法跑。解决这个问题最漂亮的办法不是优化那个内层循环而是换一个状态定义。新定义dp[k][m]表示 k 个鸡蛋、允许投掷 m 次最多能保证确定多少层楼。这个定义把次数从答案变成了状态把楼层数从状态变成了答案两个维度直接对调。推导过程很简洁。第一次投掷之后如果鸡蛋碎了我们还有 m - 1 次机会和 k - 1 个鸡蛋这部分能覆盖dp[k-1][m-1]层全部放在下面。如果鸡蛋没碎我们还有 m - 1 次机会和 k 个鸡蛋这部分能覆盖dp[k][m-1]层全部放在上面。最后再加上被投掷的那一层本身。于是dp[k][m] dp[k-1][m-1] dp[k][m-1] 1边界是dp[k][0] 0和dp[0][m] 0零个蛋一次能覆盖的楼层数当然是 0这里用 0 而不是 INF因为定义变成了能覆盖多少而不是需要几次性质完全反过来了这也是很多人在这儿写错的原因。最终答案是满足dp[K][m] N的最小 m。时间复杂度 O(K · M)而 M 最坏等于 N所以是 O(K · N)空间也是 O(K · N)。相比正向的 O(K · N²)在 N 10000、K 10 这个量级上差了整整四个数量级实测差距是跑几分钟和跑几毫秒的区别。3.2 组合数视角答案等价于找最小的 m 使 ΣC(m,i) ≥ N把上面的递推式展开你会发现一个很妙的结论dp[k][m] C(m,1) C(m,2) ... C(m,k)其中约定 i m 时 C(m, i) 0。验证一下k 1 时只剩 C(m,1) m和一个蛋线性扫 m 层完全吻合k 2、m 14 时是 C(14,1) C(14,2) 14 91 105正好对上前面说的 2 蛋 100 层需要 14 次k ≥ m 时求和等于 2^m - 1也就是蛋足够多等价于二分因为一下就能从 2^m - 1 层里用二分定位。这个公式的好处是能直接手算考试里特别管用。它还有一层直观解释可以的组合数C(m, i)表示的是在 m 次投掷里恰好碎掉 i 个蛋这种情况所能区分出的楼层数量所有可能的碎裂次数加起来就是总覆盖能力。换个说法dp[k][m]就是杨辉三角第 m 行的前 k 项之和这和每次投掷把问题分成两叉的树形结构是同一件事。有了这个公式两个极端情况的答案可以直接写出来不用跑程序。K 1 时答案是 NK ≥ ⌈log₂(N1)⌉ 时答案是 ⌈log₂(N1)⌉。后面构造测试数据的时候这两条就是免费的标杆答案。3.3 滚动数组实现与答案定位的细节二维版本写起来最直观但既然dp[k][m]只依赖第 m - 1 次的结果完全可以压成一维def super_egg_drop_1d(K, N): if N 0: return 0 K min(K, N) # 蛋多到超过楼层数没有意义截断省内存 dp [0] * (K 1) # dp[k] 表示 k 个蛋、当前 m 次能覆盖的楼层数 m 0 while dp[K] N: m 1 prev 0 # 代表 dp[k-1][m-1]k1 时它是 dp[0][m-1] 0 for k in range(1, K 1): old dp[k] # 旧值就是 dp[k][m-1] dp[k] old prev 1 prev old # 给下一个 k 用对应 dp[k][m-1] return m这段代码有几个地方值得停下来看。第一K min(K, N)是安全的截断因为 K 1 时答案最多是 N蛋的个数超过楼层数纯属浪费内存更紧的截断是min(K, ceil(log2(N1)))因为超过这个数答案就固定是二分的次数了。第二内层循环里prev的更新顺序很关键必须先把旧值存进old再赋给prev否则你在计算dp[k]的时候已经把dp[k-1]覆盖掉了结果会偏大。第三循环的上界是 N因为 K 1 时答案就是 N数组必须开到N 1不然会越界。二维版本更适合写实验报告因为表结构一眼就能看出状态之间的关系def super_egg_drop_2d(K, N): if N 0: return 0 K min(K, N) dp [[0] * (N 1) for _ in range(K 1)] # dp[k][m] m 0 while dp[K][m] N: m 1 for k in range(1, K 1): dp[k][m] dp[k][m - 1] dp[k - 1][m - 1] 1 return m写这段代码时要注意循环顺序外层必须是 m 递增内层必须是 k 递增两个顺序都不能换。因为dp[k][m]同时依赖同一行的前一列和上一行的前一列两个方向都必须是从小到大。4. 两个把 O(KN²) 压下去的优化二分查找与决策点单调4.1 固定 k 时 f(i) 是 V 形函数二分的前提如果你坚持要写正向 DP很多时候实验报告要求给出问题的最优子结构并实现那就必须在那个内层枚举上做文章。固定 k 和 n定义f(i) max( dp[k-1][i-1], dp[k][n-i] )注意 i 从 1 变到 n 的过程中两个分支的变化方向是相反的A(i) dp[k-1][i-1]随着 i 增大而单调不减因为楼层越多需要的次数越多B(i) dp[k][n-i]随着 i 增大而单调不增因为剩下的楼层越来越少。一个单调不减的函数和一个单调不增的函数取 max得到的必然是先降后升的 V 形函数严格说是非增段接非减段。这就意味着f(i)一定有唯一的一段极小值区间而我们要找的最低点就在A(i)和B(i)曲线交叉的位置附近。这个 V 形性质是二分查找能用的理论依据不是凭感觉二分的。如果你没想清楚这一点就去写二分很容易写出一个看起来能过样例、实际在大数据上错得离谱的版本。4.2 二分实现以及最优解在 lo 或 lo-1的处理我们要找的是使得A(i) B(i)成立的最小 i把这个位置记作 lo。由于函数是 V 形的最优解一定在 lo 或者 lo - 1 这两个候选里两个都算一遍取小值就万无一失了def super_egg_drop_binary(K, N): if N 0: return 0 K min(K, N) prev [0] * (N 1) # dp[k-1][*] for n in range(1, N 1): prev[n] n # k 1 的基准行 if K 1: return N for k in range(2, K 1): cur [0] * (N 1) # dp[k][*] for n in range(1, N 1): lo, hi 1, n while lo hi: mid (lo hi) // 2 if prev[mid - 1] cur[n - mid]: lo mid 1 else: hi mid best 1 max(prev[lo - 1], cur[n - lo]) if lo 1: # 平台期可能让最优解落在左边一格 best min(best, 1 max(prev[lo - 2], cur[n - lo 1])) cur[n] best prev cur return prev[N]这段代码的时间复杂度是 O(K · N · log N)空间用滚动数组压到了 O(N)。它比第 3 章的 O(K · N) 慢一个 log但优点是逻辑上完全沿着原始转移方程走推导过程和实验报告里的公式一一对应答辩的时候好解释。提示二分写完之后一定要拿只有 2 个蛋的小数据打表看一遍cur数组。2 蛋时cur[n]的增长是阶梯状的比如 1, 2, 2, 3, 3, 3, 3, 4, 4, …如果打出来是平滑的线性增长说明二分的比较方向反了。4.3 决策点单调性 爬坡理论 O(KN) 的做法还有一个更进一步的优化思路是利用决策点单调这个性质对于固定的 k最优的第一次投掷位置opt[k][n]随着 n 增大是单调不减的。这个性质可以用四边形不等式证明实验报告里如果不想展开证明至少也要用程序打印几行opt数组验证一下看到它确实是单调的再往下写。把它和 4.1 的 V 形性质结合起来就得到一个很干净的算法既然函数是 V 形的而谷底位置又随着 n 往右移动那我就不用从头枚举直接从上一层的决策点位置开始往右走一旦发现函数值开始上升就停下。def super_egg_drop_mono(K, N): if N 0: return 0 K min(K, N) dp [[0] * (N 1) for _ in range(K 1)] for n in range(1, N 1): dp[1][n] n for k in range(2, K 1): opt 1 for n in range(1, N 1): i min(opt, n) # 决策点单调从上一层的谷底开始 best 1 max(dp[k - 1][i - 1], dp[k][n - i]) best_i i while i n: # 沿谷底向右爬直到函数值不再下降 cand 1 max(dp[k - 1][i], dp[k][n - i - 1]) if cand best: best cand i 1 best_i i else: break dp[k][n] best opt best_i return dp[K][N]复杂度分析很有意思。对固定的 kn 从 1 到 N 的过程中决策点opt[k][n]从 1 单调走到最多 N每次的总步数是相邻两层决策点之差加一累加起来就是 O(N)。所以整个算法是 O(K · N) 的和第 3 章的逆向 DP 同阶。但两者各有各的好逆向 DP 空间可以压到 O(N) 而且代码短但需要你理解覆盖楼层数这个反直觉的定义决策单调版用的是最原始的正向状态定义推导过程直接对应实验报告里的公式同时又能达到线性复杂度。如果你的实验报告要求必须基于原始状态定义给出优化那就用这一版。5. 我在实现和调试中踩过的坑5.1 dp[0][n] 0 导致答案偏小的隐蔽 bug这个坑我在前面提过一次但值得单独展开因为它的隐蔽程度真的很高。现象是这样的我写完正向 DP 之后拿 2 蛋 100 层测试程序输出 10拿 3 蛋 100 层测试输出 8。这两个数字都在看起来合理的范围内不像溢出或者崩栈那么扎眼所以很容易被误认为算法没问题可能是我记错了标准答案。排查的过程是这样的。第一步我打印了完整的 DP 表重点看第 0 行。发现dp[0][*]全是 0因为 Python 里[[0]*(n1) ...]初始化之后就长这样。第二步我手动代入 n 1、k 2 算了一遍dp[2][1] 1 max(dp[1][0], dp[2][0]) 1 0 1这个是对的。第三步我算 n 2、k 2i 1时max(dp[1][0], dp[2][1]) max(0, 1) 1i 2时max(dp[1][1], dp[2][0]) max(1, 0) 1取 min 加 1 得 2也是对的。第四步我算 k 3、n 5 的时候i 1分支里出现了max(dp[2][0], dp[3][4])没问题但i 3分支里出现了max(dp[2][2], dp[3][2])还是没问题。真正出问题的是当 k 继续增大、内层用到dp[k-1][i-1]且i - 1恰好为 0 时——不对那时候dp[k-1][0]本身是 0是正确的。我把这个问题重新想了一遍才定位到真正的原因错误不在dp[0][0]而在当 k 1 且 n 0 时如果程序在内层循环里尝试走碎蛋分支。因为dp[1][n]我单独赋值成了 n所以正向 DP 的 k 1 那层是没问题的问题出在我为了代码统一把 k 1 也放进了循环里让程序自己去算dp[1][n]而此时dp[0][i-1]全是 0max就会取到另一边的值导致dp[1][n]被算成了一个很小的数然后这个错误值一路传播到所有更大的 k。修复办法有两条选哪条都行。一是把 k 1 那层单独初始化循环从 k 2 开始这也是我最后采用的做法。二是把dp[0][n]n 0设成一个足够大的整数比如N 1让max在组合蛋数为 0 的时候必然取到它从而把这条路堵死。两条路都通向正确的答案但绝对不能两条都不做。5.2 Python 里递归记忆化和三层循环的性能陷阱很多同学写 DP 喜欢用递归加functools.lru_cache因为转移方程照抄下来就行不用想循环顺序。在这道题上这个习惯会带来两个麻烦。第一个是递归深度。dp[k][n]在展开过程中会调用dp[k][n-1]、dp[k][n-2]等等虽然用了记忆化之后实际计算量是 O(K · N²)但递归调用链条的长度在最坏情况下会接近 N。当 N 10000 时Python 默认的递归上限 1000 会直接抛RecursionError。你可以手动调sys.setrecursionlimit但这只是把问题往后推深度上万之后 C 栈本身也有风险。第二个是缓存字典的开销。lru_cache每次调用都要做一次哈希查找和参数打包常数开销比数组下标访问大得多。同一组数据数组版本可能在 0.5 秒内跑完带装饰器的递归版本要跑十几秒。三层循环的问题更直接内层枚举是 n 次中间层和外面层加起来是 K · N总操作数是 O(K · N²)。K 10、N 10000 时是 5 亿次循环Python 里每次循环还要做函数调用级别的字典索引实测是分钟级的量。这种情况下最实际的做法是小数据N ≤ 200用朴素三层循环保证正确性大数据直接换第 3 章或第 4 章的优化版本。如果非要在 Python 里优化朴素版有两个立竿见影的小技巧。一是把dp[k-1]和dp[k]提前绑定到局部变量减少一层下标索引实测能快 20% 到 30%up dp[k - 1] cur dp[k] for n in range(1, N 1): best N 1 for i in range(1, n 1): v up[i - 1] if up[i - 1] cur[n - i] else cur[n - i] if v 1 best: best v 1 cur[n] best二是遇到 K 很大时提前截断因为K ceil(log2(N1))之后答案就固定了可以直接返回不用真的去算 K 层循环。这个截断在 LeetCode 那类 K 达到上百的测试里特别有用。5.3 边界与特殊输入的检查清单把边界情况整理成一张表写完代码之后照着过一遍能省掉大量调试时间。我把这几组数据的标准答案也一并列出来了其中括号里标注的是常见错误输出方便你对照排查。输入标准答案常见错误输出与原因N 0任意 K0输出 1把零层楼当成需要扔一次K 1N 100100输出 7误用了二分的结论K 2N 11输出 0忘记加投掷本身的那一次K 2N 22输出 1dp[0][n] 0的传播错误K 3N 144输出 5内层用了加法而不是 maxK 2N 10014输出 10dp[0][n] 0导致偏小K 100N 1000014栈溢出或超时用了朴素递归最后一行还能顺便验证蛋足够多就等价于二分这个结论二分的次数是 ⌈log₂(10001)⌉ 14答案是 14两者一致。这类两个不同思路得到同一个答案的交叉验证比单纯跑样例有效得多。6. 测试数据怎么造、答案怎么验6.1 小规模暴力对拍自己写的优化版本最怕的就是看起来对所以一定要准备一个逻辑绝对正确的暴力版本用来对拍。在这个问题上暴力版本最简单直接用正向转移方程写记忆化递归不做任何优化代码短到不可能写错from functools import lru_cache def brute(K, N): INF N 1 lru_cache(maxsizeNone) def dp(k, n): if n 0: return 0 if k 0: return INF if k 1: return n return 1 min(max(dp(k - 1, i - 1), dp(k, n - i)) for i in range(1, n 1)) return dp(K, N)对拍脚本的框架也很简单随机生成 K 在 1 到 5 之间、N 在 1 到 30 之间的数据跑 1000 组把暴力版和你写的优化版结果逐个比较一旦不一致就立刻打印参数退出。1000 组小数据在 Python 里几秒钟就能跑完但能覆盖到绝大多数边界分支。对拍的时候还有一个小技巧不要只比较最终答案也把 DP 表整体比较一遍。最终答案相同但表不同的情况虽然罕见但一旦出现就说明某个位置的转移有偏差而这种偏差很可能在你换一组更大的数据时就暴露出来。把表比较加上相当于把检查粒度从一个点提升到整张表。6.2 几组能手算出来的标杆数据除了对拍手算几组数据作为锚点也很有必要因为它能验证你的理解而不只是验证你的程序。这里挑三组我当年写在实验报告里的推导过程。第一组K 2、N 100答案是 14。推导方式用递减增量假设第一次在 x 层扔如果碎了还剩 x - 1 层需要 1 个蛋线性扫最坏是 1 (x - 1) x 次如果没碎第二次要往上走 x - 1 层到 2x - 1 层这样每次的增量递减 1总的覆盖能力是 x (x - 1) … 1 x(x1)/2。要让这个值不小于 100解 x(x1)/2 ≥ 100 得到 x 1414 × 15 / 2 10513 × 14 / 2 91 不够所以答案是 14。第二组K 3、N 14答案是 4。用组合数公式算dp[3][4] C(4,1) C(4,2) C(4,3) 4 6 4 14刚好等于 14而 dp[3][3] 3 3 1 7 14所以最小的 m 就是 4。第三组K 100、N 10000答案是 14。因为蛋多到用不完等价于二分⌈log₂(10001)⌉ 14。用组合数验证dp[100][14] 2^14 - 1 16383 ≥ 10000而 dp[100][13] 2^13 - 1 8191 10000所以是 14。这三组数据分别覆盖了蛋少、蛋中等、蛋多到饱和三种场景如果程序在这三组上都对基本上可以认为实现是可靠的。6.3 复杂度与实测对比表把各个版本的复杂度整理在一起写实验报告的复杂度分析章节时直接抄这张表就行。最后一列是我在笔记本上跑 K 10、N 10000 时的实际感受标注的是数量级而不是精确毫秒因为不同机器差异很大但量级关系是稳定的。实现方式时间复杂度空间复杂度实测感受朴素正向 DP三层循环O(K · N²)O(K · N)分钟级基本不可接受朴素正向 DP 滚动数组O(K · N²)O(N)内存好了时间没救二分优化正向 DPO(K · N · log N)O(N)秒级能接受决策点单调正向 DPO(K · N)O(N)毫秒级推荐逆向覆盖楼层 DPO(K · N)O(N)毫秒级代码最短组合数公式 逐 m 递推O(K · N)O(K)毫秒级适合手算验证有一个细节值得注意反向 DP 的循环次数其实是 K × M其中 M 是答案而不是 K × N。当 K 很小的时候M 可能远小于 N比如 2 蛋 10000 层的答案只有 141因为 141 × 142 / 2 10011 ≥ 10000所以它在实际运行中常常比表格里写的还要快。7. 从鸡蛋掉落往外推这类极小极大型 DP 的通用套路7.1 一眼认出极小极大型 DP 的三个特征做完整道题之后我发现这类题目其实有一套很明显的识别特征抓住这三点基本就能判断该用什么样的状态定义。第一个特征是保证和最坏情况这类词。只要题面里出现无论……都能确定、最坏情况下最少、一定能找到就说明存在一个对手模型转移方程里必然有 max 取最坏分支。第二个特征是消耗型资源。鸡蛋是消耗品碎了就少一个这种操作会损耗资源的设定往往会让状态里多一个维度比如鸡蛋个数、剩余次数、剩余容量。很多同学看到这种题第一反应是贪心但资源消耗会导致局部最优解不成立必须用 DP 或者二分答案加判定。第三个特征是决策点具有单调性。这类问题的最优决策位置通常随着问题规模单调移动这既是优化复杂度的突破口也是验证实现是否正确的信号。如果你打印出来的决策点数组是来回跳的八成是转移方程写错了。顺着这套特征去看能归到同一类的题目还有不少分割数组使最大子数组和最小LeetCode 410、爱吃香蕉的珂珂LeetCode 875、在 D 天内送达包裹的能力LeetCode 1011它们都是答案二分加可行性判定的结构判定函数里藏着 max 和 min 的组合。把它们放在一起练一遍动态规划这一章的题感会明显不一样。7.2 写实验报告时容易被扣分的地方最后说说实验报告。这道题的实验报告如果只是贴一坨能跑的代码分数通常不会太高因为老师要看的是你对问题的分析过程。我的经验是把下面几件事写清楚比代码多写两百行都管用。第一状态定义必须写清楚每个下标的含义包括它的取值范围和物理意义。dp[k][n]里的 k 是剩余的鸡蛋数而不是已经碎掉的鸡蛋数这种细节一定要在报告里说死否则后面所有的推导都会被认为是蒙对的。第二转移方程要配上文字说明尤其是max和min各自的现实含义。很多报告只写公式不写解释阅卷的人没法判断你是理解了还是抄的。第三边界条件要单独列一个表把dp[k][0]、dp[0][n]、dp[0][0]三种情况都写出来并说明理由。我在前面说过这几个地方年年有人写错。第四测试数据要给出输入—输出—验证方式三列最好附上和对拍脚本的对比结果。手算推导出来的那三组标杆数据2 蛋 100 层、3 蛋 14 层、100 蛋 10000 层一定要写进去它们能直接证明你的程序不是碰巧过的。第五复杂度分析要分别给出时间和空间并且说明为什么两个维度的上界分别是 K 和 N。如果做了优化要把优化前后的复杂度放在一起对比解释优化利用了哪条性质。我个人在这道题上最大的收获其实不是学会了某个具体的优化技巧而是第一次真切体会到状态定义的方向可以换这件事。同一道题正向定义是 O(K · N²)把次数和楼层数对调一下变成 O(K · N)代码量还更少。后来再遇到卡住的 DP 题我都会先问自己一句是不是把某个维度定义反了这个习惯比记住任何一个具体方程都值钱。