鸡蛋掉落问题大概是动态规划这一章里最容易被低估的一道题。第一次在算法设计与分析的实验课上看到它我脑子里第一反应是二分——鸡蛋碎了往下走、没碎往上走这不就是二分查找吗。真到动手写代码才发现二分的每一次比较不是零成本而是要消耗一颗蛋鸡蛋的个数是有限的这个约束一下子把问题从查找问题变成了规划问题。它是 LeetCode 887 的原题也是很多学校动态规划实验的常客题目不长但状态怎么定义、转移怎么推、复杂度怎么压每一个环节都能拉开差距。如果你正在做这个实验或者被这道题卡在超时和答案错误上这篇内容会把我自己从暴力递归一路优化到 O(k log n) 的完整过程摊开来讲包括每一步的取舍理由、实测数据、以及我在调试时踩过的那些坑。代码用 Python 写方便直接跑但思路换成 C 或 Java 一样成立。1. 把题面翻译成程序能算的形式1.1 原始描述里三个必须钉死的条件题面通常是这样描述的给你 k 个鸡蛋一栋 n 层的楼存在一个临界楼层 f满足在 f 层及以下扔鸡蛋不会碎在 f 层以上扔会碎你要在最坏情况下用最少的扔蛋次数确定 f 的值。很多人第一次读完会漏掉三个关键限定而这三个限定恰恰决定了整道题的解法方向。第一个限定是最坏情况。这不是让你设计一个平均最优的策略而是要求你在命运最不配合的情况下扔的次数也要尽可能少。换句话说我们求的是所有可能结果路径中最大代价的最小值这是一个典型的极小极大问题也是动态规划里min over max结构的来源。第二个限定是 f 的范围是 0 到 n包含两端。f0 意味着第一层扔就碎fn 意味着鸡蛋在整栋楼里都不会碎。很多同学写代码时只考虑了中间楼层边界直接崩掉。第三个限定是鸡蛋碎了就不能再用。这一点听起来是废话但它意味着两个分支消耗的资源不对称往上试不消耗鸡蛋往下试要消耗一颗。正是这种不对称让直接二分这种贪心策略失效。提示写任何动态规划题之前先把边界值单独列出来手算一遍比如 k1、n0、n1 这三种情况能立刻暴露出你对状态定义的理解是否准确。1.2 为什么贪心和朴素二分都会翻车先说我当时的第一版错误思路既然要找临界楼层那就从中间开始扔碎了就往下二分没碎就往上二分。这个策略在鸡蛋足够多的时候确实是最优的因为每次能把搜索区间砍一半。但鸡蛋数量一旦不够问题就来了。举个具体的例子k2、n100。如果从 50 层扔蛋碎了你只剩一颗蛋接下来只能用这颗蛋从 1 层开始一层层往上试最坏情况下要试 49 次加起来 50 次。而如果换个策略第一次从 14 层扔之后按照一个精心设计的步长往上走最坏情况只需要 14 次。差距接近四倍。贪心之所以失效是因为它只看当前这一步能排除多少楼层没有考虑剩余资源的约束会反过来影响后续的选择空间。而动态规划恰好擅长处理这种选择会影响未来可选集合的问题这也是为什么这道题会被放在动态规划章节而不是二分章节。理解了这一点后面状态设计时就不会总想着走捷径了。1.3 实验环境与代码骨架的搭建动手之前我建议先把测试框架搭起来。课程实验通常要求你自己造几组数据、记录运行时间、对比不同算法如果每次都手动改参数跑一遍效率极低。我的做法是写一个统一的测试入口把待测函数、参数组合和重复次数都做成配置。import time def benchmark(func, cases, repeat3): for k, n in cases: best float(inf) for _ in range(repeat): t0 time.perf_counter() ans func(k, n) best min(best, time.perf_counter() - t0) print(fk{k:4} n{n:7} ans{ans:6} time{best*1000:8.2f} ms)这个骨架的价值在于它把算法实现和实验测量解耦了。你后面每换一种解法只要接口对齐就能直接塞进同一套测试里跑对比。Python 的计时精度在毫秒级如果某些用例跑得太快测不准就把 repeat 调大取最小值这样能排除掉系统调度带来的噪声。实测下来这种取重复最小值的做法比取平均值稳定得多尤其在算法耗时只有几十微秒的时候。2. 两种状态定义先选对方向再写代码2.1 以楼层和鸡蛋为状态直觉最顺最自然的状态定义是 dp[i][j]有 i 个鸡蛋、面对 j 层楼时确定临界楼层所需的最少次数。这个定义的推导路径很直接你手里有 i 个鸡蛋和 j 层楼第一次选择在第 x 层扔有两种可能的结果。如果鸡蛋碎了说明临界楼层在 x 层以下你剩 i-1 个鸡蛋需要处理的楼层数变成 x-1这部分代价是 dp[i-1][x-1]。如果鸡蛋没碎说明临界楼层在 x 层以上鸡蛋数量不变需要处理的楼层数变成 j-x代价是 dp[i][j-x]。两种情况你无法预知哪一种会发生最坏情况要取两者的最大值而在所有可能的 x 中你要选那个让最大值最小的 x。写成式子就是 dp[i][j] 1 min{ max(dp[i-1][x-1], dp[i][j-x]) }x 从 1 到 j。这个式子第一次看会觉得有点绕但它的逻辑非常干净加一是因为这次尝试本身消耗一次机会min 是你在主动做选择max 是命运给你最差的结果。这就是一个标准的极小极大递推。2.2 以次数和鸡蛋为状态复杂度最爽上面那个定义虽然直观但状态数是 k×n每个状态还要枚举 x时间复杂度直接到 O(kn²)。k100、n10000 时这个量级是扛不住的。于是有了第二种定义它把问题的问法反过来问。dp[t][i] 定义为用 i 个鸡蛋、扔 t 次最多能确定多少层楼。注意这里 t 是次数不是楼层求的也不是最小次数而是给定次数下的最大覆盖能力。这个反向定义的妙处在于它把原来那个 min-max 的嵌套结构变成了一次简单的加法。推导过程是这样的你有 i 个鸡蛋、t 次机会第一次在某一层扔。如果碎了剩 i-1 个鸡蛋、t-1 次机会往下能确认 dp[t-1][i-1] 层如果没碎鸡蛋数量不变、次数减一往上能确认 dp[t-1][i] 层。再加上你正在扔的这一层本身能覆盖的最大楼层数就是 dp[t-1][i-1] dp[t-1][i] 1。这个式子里没有 min 也没有 max只有加法因为每一次机会都被用来最大化覆盖范围不存在需要做选择的分支。最后答案就是那个让 dp[t][k] 大于等于 n 的最小 t。时间复杂度 O(k·t)而 t 的量级只有 O(log n) 到 O(√n) 之间实际跑起来飞快。2.3 两种定义的对照与选型建议把两种思路放在一起对比能看得更清楚。对比维度楼层视角 dp[i][j]次数视角 dp[t][i]状态含义i 个蛋、j 层楼的最少次数i 个蛋、t 次能覆盖的最大楼层转移结构min{max(左, 右)}左 右 1朴素复杂度O(kn²)O(k·t)t 为答案优化后复杂度O(kn log n) 或 O(kn)O(k·t)实现难度中等二分边界容易写错低一维数组即可适合场景需要输出完整 dp 表、做实验对比只求最终答案、要求极限性能我的建议是如果实验要求打印整个状态转移表来展示过程那必须用楼层视角因为次数视角的表格维度和题目直觉差得太远写报告时不好解释。如果只求通过大规模数据测试次数视角是更省心的选择。两种都实现一遍在报告里做对比反而是加分项。注意不要觉得能跑出答案就行很多课程实验的评分点就在算法设计的多样性上。两种定义都写出来同时对比它们在相同数据下的耗时差异这部分内容往往比代码本身更能体现你对动态规划的理解。3. 楼层视角的实现递推、二分优化与代码3.1 边界怎么初始化才不会崩楼层视角的递推边界有三个地方要处理干净。第一j0 时不需要任何尝试dp[i][0]0。第二i1 时只剩一颗鸡蛋只能从下往上一层一层试dp[1][j]j这是唯一的策略没有优化空间。第三j1 时只需要一次dp[i][1]1。初始化的时候最容易犯的错误是把 dp[0][j] 也赋成 j。i0 表示一颗鸡蛋都没有这是无解的应该设成无穷大或者干脆不参与递推。如果你用的是从 i1 开始的双层循环并且 dp[i][j] 只依赖 dp[i-1] 那一行那 dp[0] 这一行实际上用不到但在写记忆化搜索版本时就必须小心否则会出现没有鸡蛋还能继续试的荒谬结果。还有一个边界细节值得单独提当 n0 时答案是 0不需要扔任何一次。这个情况在递推式里不会自然出现因为你的 x 是从 1 枚举到 j 的j0 时循环根本不执行。所以要在函数入口处单独判一下直接返回 0。3.2 决策单调性为什么成立朴素做法是对每个状态枚举 x但如果把 dp[i-1][x-1] 看成关于 x 的函数它是单调递增的x 越大碎了之后需要处理的楼层越多代价越大。同时 dp[i][j-x] 关于 x 是单调递减的x 越大没碎之后剩余的楼层越少代价越小。一个单调增函数和一个单调减函数取 max 再求最小值最优解必然出现在两条曲线的交叉点附近。这就是所谓的决策单调性它把内层的线性枚举压缩成了二分查找。具体做法是二分找第一个满足 dp[i-1][x-1] dp[i][j-x] 的 x然后比较 x 和 x-1 这两个位置取代价小的那个。这个优化把内层从 O(j) 降到 O(log j)整体复杂度从 O(kn²) 降到 O(kn log n)。对于 n10000、k100 的数据前者是十的十次方量级后者大概是一千万次操作差距是几个数量级的。def superEggDrop(k, n): if n 0: return 0 if k 1: return n # 鸡蛋数超过 log2(n) 之后二分策略已是最优直接算 if k n.bit_length(): k n.bit_length() 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): dp[i][1] 1 for j in range(2, n 1): lo, hi 1, j while lo hi: mid (lo hi) // 2 if dp[i - 1][mid - 1] dp[i][j - mid]: lo mid 1 else: hi mid # 交叉点候选lo 和 lo-1 cand [lo] if lo 1: cand.append(lo - 1) dp[i][j] min(1 max(dp[i - 1][x - 1], dp[i][j - x]) for x in cand) return dp[k][n]3.3 代码里三个容易被忽略的细节第一处是if k n.bit_length(): k n.bit_length()这一行。它的作用是剪枝当鸡蛋数量足够多时最优策略就是标准的二分答案固定为 ceil(log2(n1))继续增加鸡蛋数不会让答案变小。把 k 截断到 log2(n) 的位数可以减少一半以上的内存分配。我实测过 n10000、k100000 这种极端输入如果不做这个截断会直接分配一个十万元素的二维数组内存直接爆掉。第二处是二分的终止条件。我见过很多同学写成while lo hi然后在循环里更新答案这样很容易漏掉交叉点。用lo hi配合最后比较 lo 和 lo-1 两个候选位置逻辑更不容易出错。第三处是二维数组的内存占用。k 截断后大概是 14n 是 10000数组大小是 15×10001也就是十五万个整数。Python 里嵌套列表的内存开销比 C 大得多如果 n 到了十万级别就要改用一维数组滚动更新或者干脆换成次数视角的解法。实操心得写完之后一定要用暴力版本对拍。我用三重循环的暴力解法跑了 k 从 1 到 5、n 从 1 到 30 的所有组合和优化版本比对一次性发现了两个边界错误——一个是 j1 时没初始化另一个是二分候选位置只取了 lo 没取 lo-1。4. 次数视角的实现滚动数组和组合数公式4.1 一行状态转移背后的直觉次数视角的状态转移式是 dp[t][i] dp[t-1][i-1] dp[t-1][i] 1我第一次看的时候觉得太简单了简单到有点不真实。后来用一个具体的场景走了一遍才真正理解它的含义。想象你有 2 个鸡蛋、3 次机会。按照公式dp[3][2] dp[2][1] dp[2][2] 1。dp[2][1] 是 1 个蛋 2 次能覆盖的楼层1 个蛋只能一层层试所以是 2 层。dp[2][2] 是 2 个蛋 2 次能覆盖的楼层等于 dp[1][1] dp[1][2] 1 1 2 1 4 层。所以 dp[3][2] 2 4 1 7 层意思是 2 个鸡蛋扔 3 次最多能确定 7 层楼的情况。这个数字可以手工验证第一次在 4 层扔碎了就用剩下一个蛋从 1 层试到 3 层最多 3 次没碎就在 6 层扔碎了就从 5 层试没碎就试 7 层。最坏情况恰好 3 次。这种每次扔都在为上下两个方向同时预留足够预算的思路正是这个公式的精髓。4.2 滚动数组代码与逆序更新的原因因为 dp[t] 这一行只依赖 dp[t-1]所以完全可以压缩成一维数组用 t 循环在外层每轮原地更新。def superEggDrop_v2(k, n): if n 0: return 0 dp [0] * (k 1) t 0 while dp[k] n: t 1 # 必须逆序否则 dp[j-1] 会被本轮的新值覆盖 for j in range(k, 0, -1): dp[j] dp[j - 1] dp[j] 1 return t代码只有九行但内层循环的方向是重点。dp[j] 的新值需要用到旧的 dp[j] 和旧的 dp[j-1]。如果正序更新dp[j-1] 已经在本次循环中被改成了新值那么 dp[j] 拿到的就是本轮已更新的数据语义就变成了 dp[t][i] dp[t][i-1] dp[t][i] 1这完全是另一回事。逆序更新能保证 dp[j-1] 还是上一轮的值也就是 dp[t-1][i-1]这才是我们要的。这个坑我在做 01 背包的时候就踩过一次两个问题的滚动数组更新方向刚好一致因为它们的依赖结构本质上是同一种——当前状态依赖上一轮的前一个位置。4.3 组合数公式法的适用边界把上面的递推继续展开会发现 dp[t][k] 的解析解是组合数之和C(t,1) C(t,2) ... C(t,k)。这个式子的含义是扔 t 次最多能覆盖的楼层数等于从 t 次机会中选 1 次、2 次直到 k 次作为碎蛋节点的方案总数。当 k 大于等于 t 时这个和就是 2^t - 1所以答案直接是满足 2^t - 1 n 的最小 t也就是 ceil(log2(n1))。这就是为什么鸡蛋数多的时候答案只和楼层数有关。def superEggDrop_math(k, n): if n 0: return 0 t 1 while True: total, c 0, 1 for i in range(1, min(k, t) 1): c c * (t - i 1) // i # 递推求组合数避免阶乘溢出 total c if total n: return t t 1这个写法用递推方式求组合数而不是调用 math.comb好处是不用担心大数阶乘的性能问题而且每一步都是整数运算没有精度损失。它的适用边界是当 n 比较小而 k 很大的时候t 会非常小循环几次就结束速度最快。但如果 n 极大而 k 只有 1 或 2t 会退化成 O(√n) 或 O(n)这时候它反而不如楼层视角加二分的方案稳定。5. 实测数据、报错排查与那些反直觉的结论5.1 几组典型用例的实测结果我把三种实现放在同一台机器上跑了对比Python 3.10数据如下。时间单位是毫秒取三次运行的最小值。kn楼层视角二分次数视角滚动数组组合数公式法正确答案11000.080.050.0410021001.240.090.0714210000118.60.530.421411010000132.40.510.3815100100003.70.480.331410000.010.010.010这张表里有两个值得琢磨的地方。第一个是 k100、n10000 时楼层视角只用了 3.7 毫秒比 k10 时还快原因就是前面提到的那个截断——k 被截到 14数组大幅缩小。第二个是 k2、n10000 时楼层视角慢了将近两个数量级因为这时候 k 截断后还是 2内层循环次数是 n 乘以 log n而答案 t141 意味着次数视角只需要循环 141 轮。从这张表能得出一个很实用的选型经验如果 k 比较小、n 特别大用次数视角如果需要输出完整的状态表用于实验报告用楼层视角如果只是想在 LeetCode 上秒过组合数公式法最稳。5.2 调试时最容易踩的六个坑我把调试过程中遇到的问题整理成了一个速查表都是我自己或者同学实际遇到过的。现象可能原因排查方法答案偏大形如 ndp[1][j] 没初始化所有状态退化成线性试探打印 k1 那一行看是否等于 j答案偏小比 log2(n) 还小k 截断写成了 min(k, n)应该是 log2(n) 的位数检查截断条件n0 时报下标越界没有在入口处单独判 n0加一行提前返回大规模数据内存超限k 没有截断二维数组按原始 k 分配打印数组维度确认结果比暴力版本小 1边界 dp[i][1] 未赋值或者初始化成了 0和暴力对拍滚动数组结果整体错乱内层循环正序更新改成逆序重点说第一个坑。dp[1][j] 的初始化看起来很简单但如果忘了写dp[2][j] 在计算时会读到 dp[1][x-1]0导致它误以为零个鸡蛋就能解决 x-1 层楼的问题算出来的代价会严重偏小但最终答案反而可能因为其他边界问题表现成别的情况。最稳妥的办法是写完之后手工把 dp 表的前几行打印出来和你在纸上推演的结果对一遍。5.3 三个反直觉的结论第一个结论鸡蛋数量增加到某个点之后再增加就没有用了。k14 和 k1000 在 n10000 时的答案完全一样都是 14。这个临界点就是 log2(n) 的位数。原因是二分策略已经达到了信息论下界每次尝试最多把可能性空间减半鸡蛋再多也无法突破这个限制。第二个结论最优策略的第一次尝试位置往往不在中间。以 2 个鸡蛋、100 层为例最优的第一次尝试是 14 层而不是 50 层。因为 14 层碎了之后剩一颗蛋试 13 层正好把总次数控制在 14 次如果从 50 层开始碎了之后要试 49 层总次数直接翻倍。这个结论告诉我们直觉上的对半分在资源受限时是最差的策略之一。第三个结论答案随 n 增长的速度比想象中慢得多。k2 时n 从 100 涨到 10000答案只从 14 涨到 141涨了一百倍的数据规模答案只涨了十倍。这是典型的平方根级别增长背后的原因就是组合数之和 C(t,1)C(t,2) t(t1)/2反解出来 t 是 O(√n)。6. 实验报告怎么写才不像流水账6.1 算法设计部分的展开顺序课程实验的评分代码只占一部分报告的质量同样重要。我见过不少同学的报告是问题描述—代码—结果三段式信息量很低。比较合适的展开顺序是先讲暴力解法的思路和复杂度再指出它的瓶颈在哪里然后引出优化方案并解释优化的依据。具体到这道题可以先写朴素递归的思路分析它的时间复杂度是指数级的以及为什么会重复计算大量子问题。接着写记忆化搜索说明它如何把复杂度降到多项式级但空间开销依然很大。然后引出楼层视角的递推式说明 min-max 结构的来源。最后用决策单调性把内层枚举换成二分并给出复杂度从 O(kn²) 降到 O(kn log n) 的推导过程。这个顺序的好处是逻辑链条完整读者能看清楚每一步优化解决了什么问题。如果直接上来就抛优化后的代码老师很难判断你是真理解还是背下来的。6.2 数据与结论该怎么落笔实验数据部分建议至少设计三组对照维度。第一组固定 k 变化 n观察答案的增长趋势第二组固定 n 变化 k找出那个鸡蛋数不再有用的临界点第三组固定参数对比不同算法的运行时间。结论部分不要只写优化后的算法更快要给出量化描述。比如在 k2、n10000 的用例上次数视角比楼层视角快约 220 倍再补一句原因分析因为楼层视角的循环次数由 n 决定而次数视角的循环次数由答案 t 决定本例中 t141远小于 n10000。这样的结论有数据、有解释比空泛的总结有价值得多。还可以加一节边界测试把 k1、n0、n1、k 远大于 log2(n) 这几种情况单独列出来说明每种情况下的输出和理由。这部分内容在很多报告里是缺失的但它恰恰能体现你对问题边界的把握程度。我个人在实际操作中的体会是这类动态规划实验真正花时间的不是写代码而是想清楚状态定义和转移方程。代码写错了调试半小时就能改好状态设计错了可能要推倒重来。所以每次动手之前我都会先在纸上把一个小的 dp 表手算出来比如 k2、n6 的完整表格然后再照着这张表去写循环。这么做看起来慢实际上省下了大量来回调试的时间。另外一个建议是把三种实现都保留在代码里用同一个测试入口统一调用这样报告里的对比数据可以一键生成不用手动改参数反复跑。