这道题我最早是在一次面试准备时看到的，当时看完题面第一反应是“二分查找最坏不就是logN层吗”，等到真正动手写才发现完全不是这么回事——鸡蛋摔碎了就没了，策略会跟着剩余鸡蛋数一起变，这题表面上是“找楼层”，实际上是一个处处要取max和min的组合决策问题。后来在LeetCode 887上反复刷了几遍，又把各种解法都试了一遍，才算彻底摸透。

这篇文章就把《高楼扔鸡蛋》这道题从暴力递归到最优动态规划完整拆一遍，给你讲清楚每一条状态转移方程到底是从哪来的，为什么二分能做优化，以及最后那种O(KN)级别的反向定义解法到底妙在哪。不管你是刚开始刷动态规划、正在备战面试，还是单纯想把状态定义练扎实，这篇都值得看完。

1. 问题定义与题干拆解

1.1 先把题面翻译成“人话”

LeetCode 887的原题描述有点绕，提炼出来就是三句话：

• 你有K个鸡蛋，面前有一栋N层的楼。
• 存在一个临界楼层F，0 <= F <= N，鸡蛋从F层及以下扔下去不会碎，从F层以上扔下去一定会碎。
• 鸡蛋没碎可以重复使用，碎了就不能再用。
• 要求：无论F怎么取，你都要能用某种策略，在最坏情况下用最少的“扔鸡蛋次数”确定F。

这里有几个容易理解歪的点，我一开始就卡了很久。

第一，“最坏情况”是一个贯穿全文的前提。你不能说“我运气好，第一次扔就碎了”，你必须在最倒霉的情况下依然保证次数足够。所以你在第x层扔了一颗蛋，接下来可能出现两种结果：碎了，或者没碎。这两种结果你必须都兜住，状态转移时天然就要在两个分支里取较大的那个。

第二，F可以是0，意思是一楼扔下去也碎，也就是临界楼层在地面。这个边界会影响初始化，我们后面代码里再具体看。

第三，鸡蛋数量K可能很大，也可能很小。题目里给的范围我记得是K不超过100，N不超过10000。这就直接把纯递归的写法给堵死了，逼着你想动态规划。

1.2 一个热身例子：K=1和K=无穷

先把最简单的特例想明白，对理解后面公式很有帮助。

K=1：只有一个鸡蛋。这个最简单，因为你没有任何试错的资本，鸡蛋碎了就没了。最保险的办法就是从1楼开始一层一层往上扔，1楼不碎就去2楼，2楼不碎就去3楼。最坏情况下F=N，你得扔N次。答案就是N。

这个结论看着简单，但它告诉你一个重要事实：鸡蛋数量越少，策略就越“保守”，因为你一旦猜错就得从底层重新爬。

K无穷大：如果鸡蛋不花钱，你随便扔，那问题就退化成纯粹的二分查找。每次在中间楼层扔，根据碎没碎缩小一半范围，最坏情况是ceil(log2(N+1))次。这是这道题的最优下界，也是很多人第一反应“用二分”的原因。

但真正的题目里，K是个有限数，而且往往不够大。当你楼层很高、鸡蛋很少时，你不敢直接用二分把鸡蛋早早摔完，这就是问题的核心矛盾：时间（扔的次数）和资源（鸡蛋数量）之间要做trade-off。

1.3 错误的直觉：为什么不能直接二分

为什么不能简单地按二分找F？举个例子，K=2，N=100。

如果第一颗蛋在50楼扔，碎了，那你就只剩1颗蛋了，1楼到49楼之间你只能线性爬。最坏情况下，第一次碎在50楼，然后你从1楼一路扔到49楼，总共要扔1+49=50次。这比直接从1楼线性扔100次是好一些，但远不如“二分”的7次那么美好。

所以这个问题的真正难度在于：你每次决定在哪个楼层扔蛋时，必须同时考虑“楼下还剩多少层要确认”和“我手里还剩下几颗蛋”。楼层范围和鸡蛋数量是互相制约的两个维度。

换句话说，这不是一个一维的搜索问题，而是一个二维状态下的最优决策过程。动态规划的想法就自然浮现了：定义dp[k][n]为“k个鸡蛋、n层楼时，在最坏情况下确定F所需的最少扔鸡蛋次数”。

2. 从暴力递归到动态规划：状态与转移

2.1 状态定义与转移方程推导

假设当前有k个鸡蛋，面对n层楼，我们要选择一个楼层x（1 <= x <= n）扔一颗蛋。

• 如果鸡蛋碎了，说明临界楼层F在x层以下，我们只剩k-1个鸡蛋，接下来要面对x-1层楼。
• 如果鸡蛋没碎，说明F在x层或x层以上，我们还有k个鸡蛋，接下来要面对n-x层楼。

因为我们要保证最坏情况也能搞定，所以这两个分支里要取max，也就是当前选择x的情况下，后续还需要 max(dp[k-1][x-1], dp[k][n-x]) 次。

加上当前这次扔本身，总次数是：

cost(x) = 1 + max(dp[k-1][x-1], dp[k][n-x])

而我们可以在1到n中自由选择x，为了追求最少次数，要取min：

dp[k][n] = min_{1<=x<=n} ( 1 + max(dp[k-1][x-1], dp[k][n-x]) )

这其实就是这道题最核心、也最通用的转移方程。你后面看到的所有优化，本质上都是想让这个min的成本降下来。

2.2 边界条件怎么定

写代码之前，边界条件必须想清楚。

• dp[0][n]：0个鸡蛋，任何大于0的楼层都没法确定F，我们一般设成0，但实际搜索中不会用到。
• dp[k][0]：0层楼，不需要扔任何一次，直接返回0。
• dp[1][n]：只能线性扔，答案是n。
• dp[k][1]：只有1层楼，扔一次就能判断F是0还是1，答案是1。

有了这些边界，两层循环就可以填表了。

2.3 第一版代码：三重循环暴力DP（面试友好）

下面这是最直观的写法，复杂度O(KN^2)，在LeetCode上跑不过大用例，但用来理解思路非常合适。

def superEggDrop_brute(k: int, n: int) -> int: dp = [[0] * (n + 1) for _ in range(k + 1)] # 边界：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): best = float('inf') for x in range(1, j + 1): # 碎与不碎的worst case cur = 1 + max(dp[i - 1][x - 1], dp[i][j - x]) if cur < best: best = cur dp[i][j] = best return dp[k][n]

我建议你把这个版本亲手打一遍，然后打印一下dp表格，观察数值的变化规律。比如K=2、N=100时，结果应该是14。你会发现dp[2][j]的增量不是均匀的，而是越往后增加得越慢，这说明高层楼里鸡蛋的价值在变大。

2.4 为什么三重循环会超时

N最大10000，K最大100，O(KN^2)最坏就是100 * 10000 * 10000 = 10^10级别运算，放在任何OJ上都是不可能跑完的。

所以我们必须从转移方程本身动刀，减少“枚举x”的成本。那这个min里面到底藏着什么结构？这就引出了下一步的优化。

3. 二分优化：把O(KN^2)降成O(KNlogN)

3.1 观察两个函数的单调性

固定k和n，只看x的变化。设：

• A(x) = dp[k-1][x-1]
• B(x) = dp[k][n-x]

A(x)表示“鸡蛋碎掉”后的代价，显然x越大，楼下需要搜索的楼层越多，代价也越大，所以A(x)是单调不减的。

B(x)表示“鸡蛋没碎”后的代价，x越大，楼上剩下的楼层越少，代价越小，所以B(x)是单调不增的。

这两条曲线，一条往上走，一条往下走。它们会有个交点，或者在某些点上距离最近。而max(A(x), B(x))这条曲线的形状，是先随x增大而下降（因为B在主导，B减小），后随x增大而上升（因为A在主导，A增大），整体是一个“V”形或者“碗”形。

所以我们要找的“最优x”就在这条曲线的最低点附近，而这个最低点，正好是A(x)和B(x)“碰头”的位置。用二分去找这个临界点，比枚举所有x要快得多。

3.2 用二分逼近最优位置

二分查找的目标是：找到一个x使得A(x) >= B(x)的临界位置。更准确地说，我们希望A(x)和B(x)越接近越好。

在代码里每次取mid，比较dp[i-1][mid-1]和dp[i][j-mid]的大小：

• 如果前者大于后者，说明x取大了，鸡蛋碎掉的风险更高，“交点”在左边，往左搜。
• 如果前者小于后者，说明x取小了，楼上的代价更高，“交点”在右边，往右搜。

二轮循环结束后，lo和hi会停在临界点附近。这时我们不能直接返回dp[i][j] = 某个mid的值，因为mid已经变了。稳妥的做法是检查lo和hi两个候选点，取cost较小的那个。

3.3 二分版本代码实现

def superEggDrop_binary(k: int, n: int) -> int: dp = [[0] * (n + 1) for _ in range(k + 1)] for j in range(1, n + 1): dp[1][j] = j for i in range(1, k + 1): dp[i][1] = 1 for i in range(2, k + 1): for j in range(2, n + 1): lo, hi = 1, j # 在[1, j]范围内二分找最优x while lo <= hi: mid = (lo + hi) // 2 if dp[i - 1][mid - 1] > dp[i][j - mid]: hi = mid - 1 else: lo = mid + 1 # 检查lo和hi两个候选 best = float('inf') for cand in (lo, hi): if 1 <= cand <= j: best = min(best, 1 + max(dp[i - 1][cand - 1], dp[i][j - cand])) dp[i][j] = best return dp[k][n]

这个版本在LeetCode上就能过了，时间复杂度是O(KNlogN)，空间复杂度O(KN)。实测K=100、N=10000的数据，跑起来也就是几十毫秒级别。

3.4 为什么这里的二分是“实打实”的

有些题解里会说“对x做二分”，但这个说法很容易误导人。你要理解，我们二分搜索的对象不是最终答案，而是在搜索“A(x)和B(x)的交叉点”。因为max曲线的极值位置和交叉点是一致的，所以二分能找到最优x的近似位置。

这也解释了为什么循环结束以后要检查两个候选点lo和hi。由于循环条件是lo <= hi，结束后lo=hi+1，最优的x一定落在hi或lo附近，不会更远。取这两个位置代入转移方程算一下cost，取最小值，就是dp[i][j]的准确值。

这个“算候选点”的小细节，是很多二分优化写法里最容易出bug的地方。有些人直接拿mid去更新dp，二分结束时mid已经跑到不知道哪里去了，结果算出来完全不对。我自己第一次写的时候就在这里翻过车。

4. 更优解法：反向定义dp[k][m]，直接O(KN)

4.1 换个问法：给我一定次数，能测多少层

二分优化已经能用，但LeetCode上还有一种更高级的做法，时间复杂度可以压到O(KN)甚至更优，而且代码量反而更短。这个解法的核心是重新定义状态。

原始问法是：k个鸡蛋、n层楼，最少需要扔多少次？

反过来想：k个鸡蛋、最多允许扔m次，最多能确定多少层楼？

定义dp[k][m] = 用k个鸡蛋、最多扔m次，在最坏情况下能够“覆盖”的楼层数。

一旦dp[k][m] >= n，说明m次已经足够搞定n层，答案就是使dp[k][m] >= n成立的最小m。

4.2 递推公式的直观推导

考虑第一次扔鸡蛋。假设我们用一颗鸡蛋在某层扔，如果碎了，说明F在下方，但是鸡蛋少了一颗，剩下k-1个鸡蛋和m-1次机会；如果没碎，说明F在上方，鸡蛋还是k个，剩下m-1次机会。

关键在于：第一次扔的位置应该怎么选？为了让整体覆盖范围最大，我们要让“上方”和“下方”的可覆盖范围加起来尽可能大，同时当前这一层本身也要算进去。

于是有：

dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1

什么意思呢？

• dp[k][m-1]：鸡蛋没碎分支里，剩下k个鸡蛋、m-1次机会，还能向上覆盖dp[k][m-1]层。
• dp[k-1][m-1]：鸡蛋碎掉分支里，剩下k-1个鸡蛋、m-1次机会，还能向下覆盖dp[k-1][m-1]层。
• 那个“+1”，就是当前第一次扔的这一层，无论如何它都可以被确定。

这个公式看起来太简洁了，以至于很多人第一次看到会怀疑它是不是漏了什么。但仔细想想，它其实和前面那个dp[k][n]=min(1+max(dp[k-1][x-1],dp[k][n-x]))是等价的，只不过换了个角度，从“限制楼层数求最少次数”变成了“限制次数求最大楼层数”。

用一次行动，把当前层的两个分支全部覆盖完整，然后把剩余的资源（次数、鸡蛋数）全部投入到上下两个方向。这种“反向视角”在动态规划里非常经典，股票问题里的状态机定义也有类似的味道。

4.3 反向解法代码实现

def superEggDrop_optimal(k: int, n: int) -> int: # dp[i] 表示当前m次时，i个鸡蛋最多能覆盖多少层楼 dp = [0] * (k + 1) m = 0 # 当k个鸡蛋能覆盖的楼层数 >= n时，跳出循环 while dp[k] < n: m += 1 # 注意从大到小遍历，确保赋值时用的是上一轮的dp for i in range(k, 0, -1): dp[i] = dp[i] + dp[i - 1] + 1 return m

这段代码比二分版本短得多，但很多人第一次看会一脸懵：为什么只用了m次外层循环？为什么从大到小更新？

关键在两点：

一是从大到小的遍历顺序。如果不逆序，dp[i-1]被更新成第m轮的值后，dp[i]再用它就变成“同轮复用”，逻辑就错了。用逆序能保证dp[i] = 旧值dp[i] + 旧值dp[i-1] + 1，也就是严格对应dp[k][m]的递推。

二是外层while循环的次数。m每加1，就把所有鸡蛋数从1到k都更新一遍。因为答案一般远小于N，这个循环的次数不会很大，整体效率非常高。

实测K=100、N=10000时，这段代码运行时间在1ms级别，肉眼根本感知不到延迟。

4.4 空间复杂度与进一步优化

上面的写法已经把空间压到O(K)，如果还想再压，可以用一个一维数组滚动更新。我个人觉得这样已经足够。

如果你追求极致的时间优化，还可以注意到dp[k][m]关于m增长的速度是组合数级别的，当k很大时，m可以做到非常小。而有意思的是，这道题其实还存在一个数学解法：当k足够大时，答案直接等于ceil(log2(N+1))；当k=2时，答案约等于ceil((sqrt(1+8N)-1)/2)，因为2个鸡蛋m次最多能测m(m+1)/2层。不过这些“快速公式”不适合直接拿来做通用解法，只适合当面试时的加分项提一嘴。

5. 面试现场与刷题中的常见坑

5.1 容易踩的初始化陷阱

很多人在写O(KN^2)版本的时候，都会把dp数组初始化为inf，然后再处理边界。但如果忘记了dp[k][0] = 0这一条，后面dp[i][j]递推时一旦x=j，就会用到dp[i-1][j-1]和dp[i][0]，如果dp[i][0]是inf，整个表全炸。

建议在写dp之前，先把所有边界值都列一遍：第0列全0，第1行从1到n递增，第1列全是1。别嫌麻烦，这比之后调试半天快得多。

5.2 二分优化里最容易写错的候选判断

二分版本里，循环结束之后我用了lo和hi两个候选值做min。有同学问：直接取其中一个行不行？

理论上，如果你二分的判断条件和边界设置得足够精确，比如你是找“最后一个B >= A”的位置，那可能只用一个值就行。但为了稳妥，我建议始终保持“检查两个候选点取最小”的习惯。因为二分结束时lo和hi就在交点两侧，你无法保证一定落在A>=B还是B>A的那一边，直接取一个点有可能错过最优值。

这种“写完二分后顺手把两个边界都算一遍”的思路，在处理很多“搜索最优转折点”的题目时都能复用，比如珂珂吃香蕉、分割数组的最大值等，都可以用这个模板。

5.3 面试官最爱的追问

这道题在面试里出现频率很高，面试官通常会从易到难问三个层次：

第一个层次：K=2时你怎么做？如果只会线性扫描，他会引导你去想动态规划。

第二个层次：一般化的K和N，你能不能写dp？能写出O(KN^2)的暴力版已经算及格。

第三个层次：问你能不能优化？这里你就得把单调性分析讲清楚，说“固定k和n时，碎与不碎两个代价一个递增一个递减，所以可以用二分找交点”。能讲清楚这一层，基本就过关了。

如果面试官心情好，还可能追问一句“你还能更快吗”？这时候你就可以把反向dp[k][m]抛出来，讲一遍递推式的含义，面试官表情一般都会亮起来。

5.4 我自己刷这道题的心得

这道题我前前后后刷了不下五遍，每次隔一段时间重新写，手都会生。后来我总结出一个习惯：不背代码，靠“几个锚点”记忆。

第一个锚点是转移方程：dp[k][n] = min(1 + max(dp[k-1][x-1], dp[k][n-x]))。只要记住这个方程，暴力版本永远写得出来。

第二个锚点是单调性：A(x)增、B(x)减，所以可以用二分找交点。这能立刻把暴力版升级到O(KNlogN)。

第三个锚点是反向定义：dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1。这个公式一旦记住，最优解代码几行就能写完，还不容易出边界bug。

顺着这三个锚点，面试时就算紧张，也能一步一步接近最优解。反过来讲，最怕的就是上来就背那个几行的最优解代码，结果被问“为什么从大到小遍历”直接愣住，那就露馅了。

这道题真正的价值，不在于那个最终答案本身，而在于它训练了你“如何重新定义状态”的能力。同样一个优化目标，你既可以把楼层当作约束、次数当作目标，也可以把次数当作约束、楼层当作目标。能在这两种视角之间自由切换，你动态规划就算真正入门了。