1. 题目到底在问什么先把题意钉死高楼扔鸡蛋这道题算法圈里几乎人人都听过但真正能把题意复述准确的人并不多。它说的是给你 N 层楼和 K 个鸡蛋存在一个临界楼层 F从 F 层及以下扔鸡蛋不会摔碎从 F1 层及以上扔就会碎。你的任务是设计一套扔的方案用最少的次数把 F 精确地测出来而且算的是最坏情况下的次数。我第一次看到这题的时候脑子里蹦出来的第一个念头就是二分查找不就行了然后在纸上推了五分钟发现自己错得非常彻底。这道题之所以被反复拿出来考不是因为它需要多高深的数学而是因为它同时踩中了三个考点状态定义、递推建模、以及约束条件下最优解结构会变形这个反直觉的事实。你如果只是背下14 次这个答案遇到 K3、N1000 或者带成本的变种就直接歇菜。所以我打算从题意开始一层一层把它拆开把每一步的为什么讲清楚而不是甩一个公式让你对照抄。提示这道题的输入通常有两个参数——楼层数 N 和鸡蛋数 K。答案是一个整数表示最坏情况下所需的最少扔鸡蛋次数。别把它和期望次数最少搞混这两者的最优策略完全不同。1.1 三种常见复述版本与它们的差别在论坛和面试里这道题至少有三种不同的说法。第一种是100 层楼、2 个鸡蛋、最少几次这是最经典的版本答案是 14。第二种是给你 N 层楼、K 个鸡蛋求最少次数这是通用版需要写算法。第三种是如果鸡蛋碎了就没法再用那么怎么扔这其实是第一种的另一种口头表达本质上没有区别。这里有个容易踩的坑有人把临界点理解成第 F 层会碎有人理解成第 F 层不碎、第 F1 层才碎。这两种表述在数值上会差 1但算法结构完全一样。真正影响解法的是另一个区分——临界点 F 的取值范围是 0 到 N。F0 意味着第 1 层就碎FN 意味着所有楼层都不碎。很多人在写代码的时候忘了这两个边界导致结果偏差。我在实际推演时习惯先问自己允许的答案空间是 0 到 N 共 N1 种可能每次扔鸡蛋最多给你两种结果那么从信息量上看至少需要 log2(N1) 次。但这个下界在有鸡蛋数量限制的时候根本达不到这就是这题有意思的地方。1.2 为什么最坏情况和最少次数这两个词是关键如果只看平均次数最少最优策略和最坏情况最少是不同的。最坏情况意味着你要考虑那些偏偏在你最不想让它碎的时候碎了的倒霉场景所以策略设计要保证每一条分支的深度都被压平。这也解释了为什么最终的间隔是递减的——越往后你剩下的尝试次数越少所以每一步的跨度必须越来越小才能保证每条分支消耗的总次数不超过一个统一的上界。换个生活化的类比你要在一条没有路灯的街上找一栋特定的房子手里的手电筒只能照一小段距离并且你每问一次路人得到的答案只有在左边或在右边。这时候你不能一直对半砍因为问路本身是有代价的。鸡蛋题里的代价就是鸡蛋会碎碎了就少一个资源。这个最坏情况的约束一旦确立题目就从搜索问题变成了一个博弈问题你在和自己的运气对赌而你要保证无论运气多差总步数都不超过某个值。1.3 手算两个小例子建立直觉在写代码之前我强烈建议先手算几个小规模的情况。第一个例子1 个鸡蛋、100 层楼答案是 100 次。因为鸡蛋只有一个你只能从 1 层开始一层一层往上试碎了立刻知道答案不碎就继续。第二个例子2 个鸡蛋、2 层楼答案是 2 次。策略是先扔 1 层碎了临界点是 0没碎就扔 2 层无论碎不碎都能确定。第三个例子稍微反直觉3 个鸡蛋、100 层楼答案不是 14而是 9。因为鸡蛋多了之后你可以用更激进的分割策略。而这个增长并不是线性的——鸡蛋从 2 个加到 3 个次数下降得很快从 3 个加到 4 个下降就慢了到 7 个鸡蛋的时候已经和二分查找的 7 次完全一致了再加鸡蛋也不会更快。这个现象背后是组合数的天花板后面我会用公式严格推给你看。把这三个小例子在纸上推一遍比直接看答案有用得多因为它能让你对资源越多、策略越激进这件事产生肌肉记忆。2. 为什么二分查找在这题翻车第一次接触这题的人几乎都会先想到二分。逻辑听上去很顺每次从中间扔如果碎了就往下半区找不碎就往上半区找log2(100) 约等于 7 次。但问题出在一个致命的地方鸡蛋是消耗品。你在中间扔一次鸡蛋碎了这个鸡蛋就用掉了。接下来如果还要继续往下探你手里可能只剩一个鸡蛋而一个鸡蛋只能线性扫描。所以二分查找在这题里翻车不是因为二分本身不好而是因为它忽略了一个约束探测动作有资源成本。当你把成本模型放进来最优解的结构就整个变形了。这一点我觉得比答案本身重要得多。2.1 二分的隐含前提每次探测是免费的标准的二分查找背后有一个默认假设数组的下标访问是 O(1) 且可重复的。你可以随便访问任意位置访问多少次都不影响下次访问。数组不会因为你看了一眼就少一个元素。鸡蛋题完全违反了这个假设你每扔一次鸡蛋就可能永久损失一个探测资源。我把这个区别叫做无损探测和有损探测。二分、三分、黄金分割这些经典搜索算法全都建立在无损探测的前提下。一旦探测有损策略就必须重新设计。这也是为什么很多看上去是二分场景的工程问题实际上最优解是别的形状。注意不要因为二分在这题不适用就以为二分没用。当 K 足够大满足 K 大于等于 log2(N1) 向上取整时最优解就是二分因为你有足够多的鸡蛋去承受每次探测的损失。所以这题真正的难点在于 K 比较小的时候。2.2 鸡蛋数量如何改变最优解的结构鸡蛋数量 K 决定了策略的激进程度。K1 的时候你没有任何试错空间只能从底往上线性扫因为一旦在高层碎了你连临界点下面还有什么都没法确认。K2 的时候你有了一次奢侈可以用第一个鸡蛋做粗定位、第二个鸡蛋做细扫描。K 越大你能承受的粗定位层级越多策略就越接近二分。我画过一张心智图来理解这件事把 K 个鸡蛋想象成 K 次犯错的配额。第一个鸡蛋碎了没关系你还有 K-1 个。但每碎一个你能用的策略复杂度就降低一档。所以最优解法本质上是在分配犯错配额——把配额用在最能压缩搜索空间的地方。这也解释了一个常见疑问为什么 2 个鸡蛋的最优解不是第一次扔 50 层因为一旦碎了你只剩 1 个鸡蛋必须从 1 层往上扫 49 层总共 50 次。而如果你第一次扔 14 层碎了就扫 13 层总共 14 次。显然后者更稳。第一次扔得太高看似压缩了上方空间实则把下方空间的扫描成本拉爆了。2.3 信息论下界与资源约束下界从信息论角度看临界点有 N1 种可能每次扔鸡蛋给你 2 种结果所以理论下界是 ceil(log2(N1))。100 层对应 ceil(log2(101)) 7 次。这个下界只有在鸡蛋无限多的时候才能达到。有了鸡蛋限制之后真正的下界变了。因为一旦鸡蛋碎光你就只能用最后一个鸡蛋线性扫描这会强制拉长最坏路径。所以真实下界是信息论下界和资源约束下界的较大者。K2、N100 的情况下资源约束下界是 14比信息论的 7 大得多所以资源约束起主导作用。理解这两个下界的区别能帮你在面试里快速判断题目属于哪一类如果 K 很大就往二分想如果 K 很小就往动态规划和组合数想。这是一个非常实用的分诊思路。3. 动态规划把状态定义清楚就赢了一半这道题有两条完全不同的动态规划思路而且它们的状态定义方向相反。很多人卡住不是因为不会写循环而是因为一开始就把状态定义错了导致转移方程绕不出来。我在教别人做这题的时候最大的体会是先把状态的含义用一句人话讲清楚再动手写代码。我自己最推荐的入门路径是先搞懂逆向 DP因为它的物理意义特别直观不要问第 i 层需要多少次而是问给我 m 次机会我能确定到第几层。把方向倒过来递推关系立刻就清楚了。3.1 正向DP的状态设计第i层需要多少次正向思路是设 dp[i][j] 表示i 层楼、j 个鸡蛋最坏情况下需要多少次。转移的时候要枚举第一次扔的楼层 t从 1 到 i。扔完之后有两种情况碎了剩下 t-1 层楼和 j-1 个鸡蛋没碎剩下 i-t 层楼和 j 个鸡蛋。因为要考虑最坏情况所以取两者的最大值再加上这一次扔的动作。写成公式是 dp[i][j] 1 min over t of max(dp[t-1][j-1], dp[i-t][j])。这个方程本身没错但它的时间复杂度是 O(N²K)N 大的时候直接超时。而且它的状态含义有两个维度都在动调试的时候容易把自己绕晕。我早期写这题就是从这个式子入手的能过小数据但一旦 N 上千就卡死。后来我才明白这个写法需要配合决策单调性来优化而决策单调性的证明又是另一个坑。对于只是想搞懂原理的人我建议先跳过它。3.2 逆向DP从扔m次能覆盖多少层切入逆向思路是设 f[k][m] 表示k 个鸡蛋、最多扔 m 次能够确定的最大楼层数。这个定义一出来转移就特别自然了。第 m 次扔的时候你选择某一层扔下去如果鸡蛋碎了你损失一个鸡蛋还剩 k-1 个鸡蛋和 m-1 次机会能够向下确认 f[k-1][m-1] 层。如果鸡蛋没碎你还有 k 个鸡蛋和 m-1 次机会能够向上确认 f[k][m-1] 层。再加上你正在扔的这一层本身所以 f[k][m] f[k-1][m-1] f[k][m-1] 1。边界条件是 f[1][m] m一个鸡蛋只能一层层往上扫f[k][0] 0没机会了啥也确认不了。这个方程漂亮的地方在于它没有枚举扔哪一层这个内层循环因为 f 的定义直接回答了能覆盖多少。第 m 次的落点就在 f[k-1][m-1] 1 层这个位置是推导出来的不需要搜索。整个复杂度降到 O(KM)其中 M 是答案本身。3.3 递推式的物理含义与组合数形式把 f[k][m] 展开你会发现它可以写成组合数的和f[k][m] C(m,1) C(m,2) ... C(m,k)。这里的 C 是组合数。这个结论用数学归纳法很好证但我觉得更有价值的是理解它的物理含义。C(m,1) 表示碎 1 次的所有可能位置其实就是 m 种对应在哪一次碎C(m,2) 表示碎 2 次的所有可能位置以此类推。因为最多只能碎 k 次鸡蛋用光所以求和取到 k 项。这个视角把扔鸡蛋翻译成了从 m 次尝试里挑出若干次作为碎掉的时刻组合意义非常清晰。对于 2 个鸡蛋的情况f[2][m] C(m,1) C(m,2) m m(m-1)/2 m(m1)/2。这是一个关于 m 的二次函数所以 N 大的时候 m 大约按根号增长。对于 k 个鸡蛋当 m 远大于 k 时f 主导项是 C(m,k)所以 m 大约按 N 的 k 次方根增长。这就是为什么鸡蛋越多、收益递减的原因。4. 参数计算实战100层2个鸡蛋为什么是14次知道公式是一回事能自己动手把 14 这个数字推出来是另一回事。我建议每个学这题的人都至少手动算一遍因为算的过程会加深你对间隔递减策略的理解。下面我把完整的过程摊开你可以跟着一起算。4.1 手推等差间隔14、27、39...假设第一次在 x 层扔。如果碎了用第二个鸡蛋从 1 层往上扫到 x-1 层最坏要 x-1 次加上第一次总共 x 次。如果没碎第二次就要在更高的位置扔而且要让这一次的总消耗上界仍然是 x。第二次扔的楼层跨度要比第一次小 1因为已经用掉了 1 次机会。所以第二次落在 x (x-1) 层。如果这次碎了往下扫的范围是 x1 到 x(x-1)-1最多 x-2 次加上前面的 2 次总共还是 x 次。以此类推每次跨度减 1。于是 x 次尝试能覆盖的总楼层数是 x (x-1) (x-2) ... 1 x(x1)/2。要覆盖 100 层解 x(x1)/2 大于等于 100。x13 时是 91不够x14 时是 105够了。所以答案是 14 次。具体的扔法就是14、27、39、50、60、69、77、84、90、95、99最后到 100。你可以看到间隔从 13 一路减到 1这就是最坏情况压平的直接体现。4.2 公式法快速求解任意N与K把上面的推导推广到任意 K就得到通用的判定方法求最小的 m 使得 C(m,1) C(m,2) ... C(m,K) 大于等于 N。实现上有两种写法——一种是循环累加组合数另一种是直接对 m 做递增搜索。因为 m 的增长速度是 N 的 K 次方根级别所以搜索空间很小。举个例子N100、K3算一下m8 时 fC(8,1)C(8,2)C(8,3) 82856 92不够m9 时 f93684129够了。所以答案是 9 次和前面手算一致。再比如 N1000、K2解 m(m1)/2 大于等于 1000m44 时是 990不够m45 时是 1035够了。所以是 45 次。从这个例子能明显看出二次增长和线性增长的差距。4.3 一张表看清K1到K6的答案变化为了让你直观感受鸡蛋数量带来的收益递减我把 N100 时不同 K 的答案列成表鸡蛋数 K最少次数相比 K-1 的收益说明1100-只能线性扫描214大幅下降经典解二次增长39明显下降三次增长48小幅下降逼近二分57微小下降等于二分下界6 及以上7无收益鸡蛋多到用不完这张表的规律很值得记当 K 达到 log2(N1) 向上取整时再多的鸡蛋也不会让答案变小因为信息论下界已经把路堵死了。100 层楼的二分下界是 7所以 K 到 5 或 6 就饱和了。这个饱和点在实际工程里非常重要它告诉你不必囤积过多的探测资源配额。5. 三种代码实现与性能对照光会推公式还不够真到写代码的时候不同的写法在可读性和性能上差别很大。我整理了三种实现分别是记忆化搜索版、逆向 DP 版、以及数学公式版。它们对应三种不同的理解层次你可以按需选用。所有代码都用 Python 写逻辑直接容易改成其他语言。5.1 记忆化搜索版最好懂from functools import lru_cache def super_egg_drop(k, n): lru_cache(maxsizeNone) def f(k, m): # k 个鸡蛋, 最多 m 次, 能确定的最大楼层数 if m 0: return 0 if k 1: return m return f(k - 1, m - 1) f(k, m - 1) 1 m 0 while f(k, m) n: m 1 return m这段代码几乎是公式的直译f 的边界和转移都一目了然。它的缺点是递归深度和缓存数量会随着 m 增长N 特别大的时候内存吃紧。不过在 N 到几千的量级完全够用面试手写也很快。5.2 逆向DP滚动数组版好写的工程解def super_egg_drop(k, n): # dp[i][j]: i 个鸡蛋扔 j 次能确定的最大楼层数 if n 0: return 0 k min(k, n) # 鸡蛋数超过 log2(n)1 的部分没有意义 dp [[0] * (n 1) for _ in range(k 1)] for j in range(1, n 1): dp[1][j] j for j in range(1, n 1): for i in range(2, k 1): dp[i][j] dp[i - 1][j - 1] dp[i][j - 1] 1 if dp[k][j] n: return j return n这个版本用二维表存 f 的值按次数 j 递增填表一旦 dp[k][j] 覆盖到 n 就返回。它把搜索答案 m这一步合并进了填表过程是工程上最常用的写法。注意 dp 的第二维开到 n1是因为最坏情况下的次数最多是 n一个鸡蛋线性扫数组不会越界。5.3 数学公式版O(K)常数级def super_egg_drop(k, n): m 1 while True: total 0 c 1 # C(m, i) 的累乘值 limit min(k, m) for i in range(1, limit 1): c c * (m - i 1) // i total c if total n: return m m 1这段代码直接套用组合数求和公式内层循环只跑到 min(k, m)所以总的复杂度是 O(K·M)其中 M 是答案。因为组合数用递推的方式累乘不会出现阶乘溢出的问题。实测在 N10^9、K100 这种量级下也是毫秒级返回非常适合竞赛和在线判题。5.4 三种实现对照表实现方式时间复杂度空间复杂度适用场景上手难度记忆化搜索O(K·M)O(K·M)理解原理、面试低逆向 DPO(K·N)O(K·N)工程实现、中等 N中数学公式O(K·M)O(1)大 N、竞赛中高表格里的 M 表示最终答案。你会发现数学公式版的空间是常数级这是它最大的优势。不过它需要你对组合数递推足够熟悉写错了容易在边界上翻车。我个人的建议是先把记忆化搜索写对再用逆向 DP 打底最后用数学公式做性能优化。6. 常见坑点与面试现场实录这道题看着简单但真到写代码和面试的时候坑点相当密集。我踩过的、见过的坑加起来能列一长串这里挑最有代表性的几个讲顺便说说面试里怎么组织语言才能把面试官说服。6.1 边界条件清单第一类坑是边界。n0 的时候答案应该是 0因为没有任何楼层需要探测但很多模板会返回 1 或者死循环。k1 的时候答案就是 n这个要单独处理不然递归会无限展开。还有 k 大于 n 的情况理论上鸡蛋数超过楼层数时最优解是二分但如果你直接按 K 去开数组会浪费空间所以要先做 k min(k, n) 的截断。第二类坑是数组下标。用 dp[i][j] 表示 i 个鸡蛋、j 次机会的时候dp[i][0] 必须全为 0dp[1][j] 必须等于 j。填表顺序必须是先 j 后 i因为 dp[i][j] 依赖 dp[i][j-1] 和 dp[i-1][j-1]两者都在更小的 j 上。顺序写反会读到脏数据。第三类坑是溢出。用组合数公式时如果直接算阶乘再相除m 稍大就会溢出必须用 c c * (m-i1) // i 这种边乘边除的递推方式保证中间结果始终是整数。6.2 高频变种题最经典的变种是给定 N 层楼问最少需要多少个鸡蛋才能保证在允许 m 次内测出临界点。这其实是原题的反函数把 f[k][m] 大于等于 N 解出最小的 k 就行。第二个变种是扔鸡蛋有成本碎的代价比没碎大这时候转移方程里的 max 要换成加权和策略会偏向尽量少碎鸡蛋答案可能和原题不一样。第三个变种是楼层不是均匀的有些楼层更容易成为临界点这就引入了概率变成了期望最优问题得用决策树或者马尔可夫决策过程来建模难度上了一个台阶。第四个变种是只有一次机会确认但可以提前观察本质上是把探测动作拆成了观测和验证两类属于带额外信息的搜索问题。6.3 面试时怎么讲面试里遇到这题千万不要一上来就写公式。正确的节奏是先用一句话确认题意特别要确认最坏情况和鸡蛋碎了就不能用这两个点。然后手算 1 个鸡蛋和 2 个鸡蛋的小例子让面试官看到你的思路。接着抛出二分为什么不行这个反例展示你对约束的敏感度。最后再给出 DP 的状态定义一步一步推到转移方程能写代码就写写不完就把复杂度分析讲清楚。有个小技巧是把状态定义写在纸上并大声念出来f[k][m] 表示 k 个鸡蛋扔 m 次能覆盖的最大楼层数。只要这句话说对了后面基本不会跑偏。如果面试官追问优化你就引到组合数求和把复杂度从 O(K·N) 降到 O(K·M)。这套流程我面过几次反馈都不错。7. 这道题在真实工程里的影子很多人觉得扔鸡蛋就是个纯数学游戏实际工作中用不上。我一开始也这么想后来发现它的模型结构在很多工程场景里都在悄悄出现只是换了个名字。理解它能帮你在面对资源有限、探测有损的问题时第一反应就找对方向。7.1 有限预算下的最优探测最典型的场景是有限预算下的探测。比如你有一个线上服务每次给它加压测试都可能把它打挂而打挂一次要花时间恢复。你手头的崩溃配额是有限的想找到一个容量临界点怎么设计加压梯度最省事这和扔鸡蛋就是同一个模型加压次数是扔的次数崩溃是鸡蛋碎配额是鸡蛋数梯度就是楼层的间隔。答案的思路也一致先大步长粗定位再逐步收窄步长保证最坏情况下总次数有上界。很多做容量规划的同学凭直觉采用的递减梯度其实就是这题的等差间隔策略。知道它背后的数学保证你在做参数设计时会更有底气。再比如 A/B 测试的预算分配、熔断阈值的二分试探、缓存淘汰策略的探测阶段都能看到有损探测的影子。题目本身是玩具但模型是通用的。7.2 与剪枝、贪心、二分的关系从算法思想上看这道题几乎把几个经典范式都串了一遍。逆向 DP 的核心是换一个方向定义状态这本质上是一种剪枝——把原本要枚举落点的 O(N) 层循环用状态的物理含义直接消掉等于剪掉了整棵决策树的子节点。等差间隔的策略体现的是贪心思想每一步都尽量跳得远但必须保证最坏路径不超上界。这个贪心是可以证明最优的因为它等价于把上界平均分配到每条分支上。而当鸡蛋数足够多时最优解退化成二分。所以你可以把这道题理解成一个从线性到二分的连续谱K1 在最左端K 足够大在最右端中间是各种组合数形态。理解这个谱比记住某个具体答案有价值得多。7.3 什么时候该用哪种解法如果你只是要在面试里回答记忆化搜索版足够如果你要在生产代码里算一个实际参数逆向 DP 版最稳如果你要处理 N 特别大的场景数学公式版是唯一选择。判断标准很简单看 N 的量级和 K 的大小。N 小于一万、K 任意DPN 上十亿、K 几十公式。还有一点经验如果 K 大于 log2(N1) 向上取整直接返回二分答案 ceil(log2(N1))不用走完整套 DP。这个判断能在很多在线判题里帮你省掉大量时间因为测试用例里经常藏着 K 很大的情况。我个人在做参数估算时的习惯是先用公式法算出理论下界再用手推的等差间隔验证一遍两边对上了才敢用。这个双验证的习惯帮我避开了不少边界上的低级错误尤其是在写组合数递推的时候手推一遍能很快发现是不是漏了某一项。最后再分享一个小技巧把 f[k][m] 的那张表打印出来看你会发现它本质上就是一个变形的杨辉三角每一行的和对应能覆盖的楼层。用这个视角去记忆递推式比死记公式牢靠得多。
