我第一次做这道题的时候第一反应是二分。毕竟n层楼、要找一个临界楼层二分不是最自然的思路吗结果写完就发现问题了鸡蛋是会碎的而且碎了不能捡回来。这个“资源会消耗”的属性让问题从普通查找变成了带约束的决策问题。LeetCode 887题“鸡蛋掉落”最磨人的地方就在这里它不像普通二分那样只关心中间位置还要考虑鸡蛋碎了之后你还有多少资本继续试。这一篇我准备把两种官方思路完整拆开讲透先讲顺着楼层思考的正向动态规划再讲官方题解更推荐的“倒过来数移动次数”方法。保证你看完后能自己把两种代码都写出来也搞明白为什么第二种方法要快这么多。两种方法的代码我都会给出还会附带我实际跑用例时踩过的边界坑适合正在刷动态规划的读者反复看。1. 先别急着写代码把“最坏情况”和“策略”翻译成状态1.1 题目里容易漏掉的两个限定词原题描述很短有k个鸡蛋n层楼存在一个临界楼层F。鸡蛋在F层及以下不会碎在F层以上会碎。目标是用最少的实验次数保证能确定F。这里有两个词很容易被轻轻放过一个是“最坏情况下”一个是“确定临界楼层”。“最坏情况下”的意思是我们选定一种策略后不管临界楼层F藏在哪个位置这个策略的总实验次数都要有一个上限我们要让这个上限尽可能小。它不是算期望不是算平均而是算最差的那一种情况。你选了一个不错的策略但如果F恰好落在某个尴尬位置导致实验次数特别多那这个尴尬位置也是要算进代价里的。“确定临界楼层”听着简单实际上包含了一种情况鸡蛋从第1层扔下去就碎了这时候F0鸡蛋扔到第n层都没碎这时候Fn。也就是说F一共有n1种可能取值。很多初学者会默认F一定在1到n之间这个习惯会让你在推导边界条件时莫名其妙地少算一层。1.2 为什么不能直接用普通二分我们来做一个小实验。假设只有一个鸡蛋n100层。你敢直接去50层扔吗如果不碎好说上面还有50层要试如果碎了鸡蛋没了而下面的49层里任意一层都可能是临界楼层但你没有任何鸡蛋可用来继续测试了。所以一个鸡蛋的情况根本不能二分只能从第1层开始一层一层往上试最坏需要100次。再假设鸡蛋非常多比如n100层给你100个鸡蛋。这时候直接二分当然可以因为每次碎了都还有足够多的鸡蛋继续试所以问题的答案接近7次。但鸡蛋数量不够多的时候二分策略不一定是最优的你可能会在某个区间内因为鸡蛋不够用而被迫改成逐层试导致总次数增加。这题的难度就在于鸡蛋数量k是一个有限资源每碎一次你对后续区域的探测能力就下降一档。所以“策略”需要把鸡蛋的消耗情况考虑进去普通二分只是一个特例。1.3 一个可以贯穿全题的抽象视角两种官方方法本质上都在做同一件事把“给定鸡蛋数k实验次数m最多能确定多少层楼”算出来。方法一正向推楼层方法二反向推次数。你想想看如果我能回答“用k个鸡蛋允许做m次实验最多能覆盖多少层楼”这个问题那么我只需要从小到大增加m找到第一个覆盖楼层数大于等于n的m它就是答案。这就是第二种方法的雏形也是第一种方法推导过程中的关键工具。2. 方法一正向动态规划加二分把O(kn²)压到O(knlog n)2.1 状态定义与转移方程的推导过程方法一顺着正常思路来用dp[i][j]表示i个鸡蛋、j层楼时在最坏情况下确定临界楼层所需的最小实验次数。这个状态定义是最直观的维度就是输入给的两个变量。现在假设我在第x层做一次实验1≤x≤j。这次实验有两种结果。第一种结果鸡蛋碎了。说明临界楼层F一定小于x也就是在下面这x-1层里。鸡蛋碎了一个手里还剩i-1个鸡蛋需要解决的子问题是dp[i-1][x-1]。第二种结果鸡蛋没碎。说明F大于等于x也就是临界楼层还在上面的j-x层里。鸡蛋一个没少手里还有i个鸡蛋需要解决的子问题是dp[i][j-x]。这次实验本身已经用掉一次次数所以总代价是1加上后续子问题的代价。最坏情况取两者中的较大值因为命运会安排更差的那一边发生。最后我们遍历x选一个让这个最坏值最小的楼层作为第一次实验位置。于是转移方程就出来了dp[i][j] 1 min(1≤x≤j) max(dp[i-1][x-1], dp[i][j-x])这个方程是整个方法一的灵魂。你要注意dp[i][j-x]这个子问题它和dp[i][j]是同一个i只是楼层数变小了。这提醒我们计算第i行的时候j要从小到大算因为dp[i][j]会依赖dp[i][j-1]、dp[i][j-2]这些更小的j。2.2 边界条件怎么定边界条件决定了整个DP表的地基。dp[i][0]很好理解0层楼不用做任何实验答案就是0。dp[1][j]等于j这个也直观只有1个鸡蛋不敢跳着试只能从第1层开始一层一层扔最坏情况是临界楼层在最后一层所以需要j次。dp[0][j]严格来说不合法因为0个鸡蛋什么都测不了但我们的状态不会走到这里循环里也没必要单独处理。还有一个隐藏边界是dp[i][1]只有1层楼不管几个鸡蛋扔一次就行。用递推也能算出来不会出错但心里要清楚。2.3 发现max函数是单峰二分查找可行如果直接按照转移方程暴力枚举x那么对于每一个(i, j)都要遍历j个位置总复杂度是O(kn²)。在n最大可以到10000、k最大可以到100的题目范围里这个复杂度完全不能接受。优化点在于观察max(dp[i-1][x-1], dp[i][j-x])的形状。先看dp[i-1][x-1]这个部分。x越大楼下需要检测的楼层数x-1越多而鸡蛋数量不变所以这个值关于x单调不减。再看dp[i][j-x]这个部分。x越大楼上剩下的楼层数j-x越少所以这个值关于x单调不增。一个单调递增的函数和一个单调递减的函数取最大值结果是什么样的它一定是一个“先下降、后上升”的离散单峰函数。在交叉点附近max取到最小值。这就可以用二分了。我只需要找到第一个满足dp[i-1][x-1] dp[i][j-x]的位置最优点一定在这个位置x或者它的前一个位置x-1附近。因为在那之前max完全由递减的dp[i][j-x]决定值随着x增大而减小在那之后max完全由递增的dp[i-1][x-1]决定值随着x增大而增大。最小值就卡在这两段中间。这个二分优化把每个状态的枚举代价从O(n)降到了O(log n)总复杂度来到O(knlog n)。对于n10000这个量级在一秒多内能轻松跑完。2.4 完整实现与边界处理我把代码贴出来用的是Python逻辑最好读def superEggDrop(k: int, n: int) - int: dp [[0] * (n 1) for _ in range(k 1)] for i in range(1, k 1): for j in range(1, n 1): if i 1: dp[i][j] j continue 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 x lo dp[i][j] 1 max(dp[i - 1][x - 1], dp[i][j - x]) # 最优点可能在前一个位置补一次比较 if x 1: dp[i][j] min( dp[i][j], 1 max(dp[i - 1][x - 2], dp[i][j - x 1]) ) return dp[k][n]值得注意的地方有两个。一个是二分找到的位置x本身就是候选但离散函数不保证交叉点正好落在整数楼层上所以最优解也可能是x-1。这就是代码末尾补一次比较的原因。不要小看这一步我最初实现时只取了x结果在部分用例上会差一次后来才意识到要检查邻居。另一个是j的循环顺序。因为dp[i][j]在二分中会访问dp[i][j-mid]而j-mid永远小于j所以只要j从小到大算dp[i][j-mid]就已经是这一轮的已知值了可以直接使用。2.5 复杂度与空间优化说明时间上方法一在n10000、k100时大概是100层循环每层里对每一层楼做一次14次左右的二分总共约一千四百万次比较完全可用。空间上代码用了二维数组大小是(k1)·(n1)。实际跑的时候这个数组可能会到几十MB。如果不喜欢可以只保留上一行和当前行因为dp[i][j]只会用到dp[i-1][...]和dp[i][...]不会往回跳两行。用两个数组滚动就能把空间降到O(n)。我保留二维写法主要是为了讲解直观实际提交时可以自行改掉。3. 方法二倒过来数移动次数用“覆盖楼层数”直接逼近答案3.1 把状态改成“m次移动最多能覆盖多少层”方法一虽然已经能过题但还不是最优的官方做法。官方更推荐第二种思路与其维持“给定鸡蛋数和楼层数求最少次数”这个方向不如反过来定义状态。设f[i][m]表示用i个鸡蛋最多允许m次移动最多能确定多少层楼的临界楼层。这里的“确定”仍然意思是无论临界楼层藏在这段范围内的哪一层都能准确找到它。这个状态的神奇之处在于dp数组里根本没有“楼层数n”这个维度。每次m加1我们计算新的覆盖范围一旦f[k][m]大于等于n就说明m次移动已经够了答案就是当前的m。3.2 状态转移的几何理解当前层、碎、不碎我第一次看到转移方程的时候觉得它简洁得不像话f[i][m] f[i-1][m-1] f[i][m-1] 1为什么是这个式子我拆开说。假设你有i个鸡蛋、m次移动。你肯定不会随便乱扔你会先选一个合适的楼层作为第一次实验点。关键在这个“合适的楼层”应该如何选。如果你从某一层开始扔而这枚鸡蛋碎了那么你已经确定临界楼层在这层以下并且手上只剩i-1个鸡蛋、m-1次移动。所以在当前层以下你最多还能覆盖f[i-1][m-1]层。如果鸡蛋没碎那么临界楼层在这层以上你手头还是有i个鸡蛋但移动次数只剩m-1次。于是在当前层以上你最多还能覆盖f[i][m-1]层。还没完。你自己扔掉的那一层本身已经做了一次实验这一层也已经被你掌握了。不管碎没碎这一层都是安全覆盖的范围所以还要加1。三层加起来就是完整的覆盖范围。这个解释比正向DP省事得多关键在于放弃了枚举“第一次扔哪一层”。它不需要知道具体扔哪层只需要知道“最多能覆盖多少层”。因为覆盖范围是一个区间你只需要在覆盖边界处安排第一次实验剩下的交给递归。另一个角度是状态转移没有“max”也没有“min”只是一个简单的加法。这在使用中极其舒服也不需要二分。3.3 滚动数组实现为什么倒序遍历i是正确的理论上f是一个二维表第一维i最大是k第二维m最大是答案。但实际写代码可以只用一维数组因为每一轮m只依赖上一轮m-1的数据。核心代码是这个def superEggDrop(k: int, n: int) - int: dp [0] * (k 1) # dp[i] 表示当前移动次数下i个鸡蛋最多覆盖多少层 ans 0 while dp[k] n: ans 1 # 注意从大到小更新 for i in range(k, 0, -1): dp[i] dp[i - 1] dp[i] 1 return ans我第一次写的时候不小心写成了从小到大更新结果答案完全不对。原因在于更新方向。假设当前正在计算第ans次移动。dp[i]在更新前保存的是上一轮m-1的结果。我们要用dp[i-1]和dp[i]这两个上一轮的值算新的dp[i]。如果从小到大更新那么算dp[1]的时候没问题算dp[2]的时候用的dp[1]已经是这一轮的新值了丢了上一轮的信息整个递推就被污染了。反过来从大到小更新计算dp[i]时dp[i-1]还没被这一轮改动过仍然是上一轮的结果。这样每个鸡蛋数都是从上一轮干净地推到这一轮的。这个细节也是面试官最爱追问的点建议当成肌肉记忆记住。3.4 复杂度分析为什么它不依赖n这个规模方法二的复杂度看起来是O(k·ans)其中ans是最终答案。这答案大小有多少呢当k1时ansn但此时循环里的for只执行1次所以复杂度是O(n)本质就是逐层试。当k比较大时比如k100n10000答案其实在十几左右。因为50个鸡蛋以上的情况下m次移动能覆盖的楼层数基本上是2的m次方这个量级。m14时2的14次方是16384已经超过10000了。所以方法二在这种输入下几乎是瞬间出结果。从整体来看方法二是好于方法一的。方法一不管答案是多少都要把k行、n列的DP表填完复杂度固定为O(knlog n)。而方法二只计算到答案那一轮为止对大规模楼层的适应性更强。这也是官方推荐它的核心理由楼层数n不再是主导复杂度的因子鸡蛋数和最终答案才是。3.5 用组合数公式加深印象方法二还有一个数学解释可以用来验证代码正确性。固定移动次数m、鸡蛋数k时最多可以覆盖的楼层数等于C(m,1) C(m,2) ... C(m,k)这里的C表示组合数。这个公式和递推是等价的因为递推式正好满足帕斯卡恒等式C(m,i) C(m-1,i-1) C(m-1,i)。举个例子k2、m3时C(3,1)C(3,2)336。我们用递推验证f[2][3] f[1][2]f[2][2]1 231 6。一致。平时刷题不需要背公式但了解这个角度对理解为什么答案只和鸡蛋数、移动次数有关会有很大的帮助。4. 两种方法放在一起比时间、空间、边界和易错点4.1 复杂度与适用场景对比对比维度方法一正向DP二分方法二逆向移动次数DP状态定义给定鸡蛋数和楼层数求最少次数给定鸡蛋数和移动次数求最多覆盖楼层数时间复杂度O(knlog n)O(k·ans)ans通常远小于n空间复杂度O(kn)可优化到O(n)O(k)代码难度中等需要理解二分边界简单但思路跳跃较大对超大n的适应性一般强实际刷题时两个都能过方法二明显更简洁。但方法一也不是白学的它的转移方程描述了原问题的结构很多第一次接触这题的读者会更先接受方法一。4.2 四个常见边界错误我全踩过第一个错误是k1时直接套方法二。方法二的while循环能正确处理k1时每次只更新dp[1]dp[1]逐年递增最后返回n。但如果你在方法一里忘记单独处理i1这一行二维表里全是0二分也会乱套。第二个错误是n1这种极端小数据。n1时不管k是多少答案都是1。方法二循环第一次dp[k]就会变成1退出返回1没事。方法一也自然得到1。第三个错误是忽略F0或Fn的情况。上面说过了临界楼层有n1种可能。虽然两种DP公式都能自动覆盖这个情况但如果你写二分时把区间含义理解成“F一定在1到n之间”就可能在解释边界时出错。第四个错误是方法二的while循环条件。有人会写成dp[k] n等号漏掉。dp[k]等于n时已经刚好覆盖全部楼层应当立刻返回当期ans。漏掉等号会让答案多算一次。4.3 自测用例和手算过程提供几个我常用的验证用例你可以自己跑一遍。k1, n7答案是7。只有一个鸡蛋老老实实从第1层试到第7层。k2, n2答案是2。第一次扔第1层碎了F0没碎再扔第2层。两步确定。k2, n6答案是3。f[2][3]63次移动足够覆盖6层。k3, n14答案是4。f[3][4]14。这个用例用来确认大规模递归没有算漏。k2, n100答案是14。这是鸡蛋掉落问题的经典例子2个鸡蛋100层最坏14次。你拿代码跑一下返回14就说明基本没写错。4.4 这类DP问题通用的三个经验第一先想清楚状态里放的是“最小代价”还是“最大覆盖范围”这决定了转移是带min/max还是带加法。后者常常让问题变简单。第二看到两个单调函数取max一定要条件反射地想到二分。很多看似需要枚举的DP都能靠单调性优化一步。第三滚动数组更新时先确认依赖方向。如果新状态依赖同一个数组里的旧状态通常要倒序遍历。这个经验在01背包问题里也适用方法论是相通的。5. 写在最后的一点扩展思考刷完这题之后我最大的感受是一道好的动态规划题不会只考你公式推导它会逼你换一个思考维度。方法一和方法二唯一的区别就是“维度选择”一个把楼层数当主变量一个把移动次数当主变量结果复杂度天差地别。我在实际练习中养成了一个习惯每道DP题写出基础版本之后都会问自己一句“这个状态能不能反过来定义”。比如把“给定范围内求最优次数”改成“给定次数求最大覆盖范围”很多看起来复杂的题会瞬间清晰。鸡蛋掉落就是最典型的例子。最后送大家一个小技巧如果你在面试或者模拟笔试时卡住了可以先从k1和k非常大两个极端场景推答案。k1的答案就是nk非常大时答案接近二分次数。这两条线能帮你确认DP表的正确性也能帮你和面试官快速对齐题意。我自己遇到这道题的时候就是先用这两个极端把思路校准再进入状态设计整个推导会顺畅很多。