这道题我最早是在一次面试准备时看到的当时看完题面第一反应是“二分查找最坏不就是logN层吗”等到真正动手写才发现完全不是这么回事——鸡蛋摔碎了就没了策略会跟着剩余鸡蛋数一起变这题表面上是“找楼层”实际上是一个处处要取max和min的组合决策问题。后来在LeetCode 887上反复刷了几遍又把各种解法都试了一遍才算彻底摸透。这篇文章就把《高楼扔鸡蛋》这道题从暴力递归到最优动态规划完整拆一遍给你讲清楚每一条状态转移方程到底是从哪来的为什么二分能做优化以及最后那种O(KN)级别的反向定义解法到底妙在哪。不管你是刚开始刷动态规划、正在备战面试还是单纯想把状态定义练扎实这篇都值得看完。1. 问题定义与题干拆解1.1 先把题面翻译成“人话”LeetCode 887的原题描述有点绕提炼出来就是三句话你有K个鸡蛋面前有一栋N层的楼。存在一个临界楼层F0 F N鸡蛋从F层及以下扔下去不会碎从F层以上扔下去一定会碎。鸡蛋没碎可以重复使用碎了就不能再用。要求无论F怎么取你都要能用某种策略在最坏情况下用最少的“扔鸡蛋次数”确定F。这里有几个容易理解歪的点我一开始就卡了很久。第一“最坏情况”是一个贯穿全文的前提。你不能说“我运气好第一次扔就碎了”你必须在最倒霉的情况下依然保证次数足够。所以你在第x层扔了一颗蛋接下来可能出现两种结果碎了或者没碎。这两种结果你必须都兜住状态转移时天然就要在两个分支里取较大的那个。第二F可以是0意思是一楼扔下去也碎也就是临界楼层在地面。这个边界会影响初始化我们后面代码里再具体看。第三鸡蛋数量K可能很大也可能很小。题目里给的范围我记得是K不超过100N不超过10000。这就直接把纯递归的写法给堵死了逼着你想动态规划。1.2 一个热身例子K1和K无穷先把最简单的特例想明白对理解后面公式很有帮助。K1只有一个鸡蛋。这个最简单因为你没有任何试错的资本鸡蛋碎了就没了。最保险的办法就是从1楼开始一层一层往上扔1楼不碎就去2楼2楼不碎就去3楼。最坏情况下FN你得扔N次。答案就是N。这个结论看着简单但它告诉你一个重要事实鸡蛋数量越少策略就越“保守”因为你一旦猜错就得从底层重新爬。K无穷大如果鸡蛋不花钱你随便扔那问题就退化成纯粹的二分查找。每次在中间楼层扔根据碎没碎缩小一半范围最坏情况是ceil(log2(N1))次。这是这道题的最优下界也是很多人第一反应“用二分”的原因。但真正的题目里K是个有限数而且往往不够大。当你楼层很高、鸡蛋很少时你不敢直接用二分把鸡蛋早早摔完这就是问题的核心矛盾时间扔的次数和资源鸡蛋数量之间要做trade-off。1.3 错误的直觉为什么不能直接二分为什么不能简单地按二分找F举个例子K2N100。如果第一颗蛋在50楼扔碎了那你就只剩1颗蛋了1楼到49楼之间你只能线性爬。最坏情况下第一次碎在50楼然后你从1楼一路扔到49楼总共要扔14950次。这比直接从1楼线性扔100次是好一些但远不如“二分”的7次那么美好。所以这个问题的真正难度在于你每次决定在哪个楼层扔蛋时必须同时考虑“楼下还剩多少层要确认”和“我手里还剩下几颗蛋”。楼层范围和鸡蛋数量是互相制约的两个维度。换句话说这不是一个一维的搜索问题而是一个二维状态下的最优决策过程。动态规划的想法就自然浮现了定义dp[k][n]为“k个鸡蛋、n层楼时在最坏情况下确定F所需的最少扔鸡蛋次数”。2. 从暴力递归到动态规划状态与转移2.1 状态定义与转移方程推导假设当前有k个鸡蛋面对n层楼我们要选择一个楼层x1 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为了追求最少次数要取mindp[k][n] min_{1xn} ( 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)] # 边界k1时只能线性试 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表格观察数值的变化规律。比如K2、N100时结果应该是14。你会发现dp[2][j]的增量不是均匀的而是越往后增加得越慢这说明高层楼里鸡蛋的价值在变大。2.4 为什么三重循环会超时N最大10000K最大100O(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)。实测K100、N10000的数据跑起来也就是几十毫秒级别。3.4 为什么这里的二分是“实打实”的有些题解里会说“对x做二分”但这个说法很容易误导人。你要理解我们二分搜索的对象不是最终答案而是在搜索“A(x)和B(x)的交叉点”。因为max曲线的极值位置和交叉点是一致的所以二分能找到最优x的近似位置。这也解释了为什么循环结束以后要检查两个候选点lo和hi。由于循环条件是lo hi结束后lohi1最优的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(1max(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这个循环的次数不会很大整体效率非常高。实测K100、N10000时这段代码运行时间在1ms级别肉眼根本感知不到延迟。4.4 空间复杂度与进一步优化上面的写法已经把空间压到O(K)如果还想再压可以用一个一维数组滚动更新。我个人觉得这样已经足够。如果你追求极致的时间优化还可以注意到dp[k][m]关于m增长的速度是组合数级别的当k很大时m可以做到非常小。而有意思的是这道题其实还存在一个数学解法当k足够大时答案直接等于ceil(log2(N1))当k2时答案约等于ceil((sqrt(18N)-1)/2)因为2个鸡蛋m次最多能测m(m1)/2层。不过这些“快速公式”不适合直接拿来做通用解法只适合当面试时的加分项提一嘴。5. 面试现场与刷题中的常见坑5.1 容易踩的初始化陷阱很多人在写O(KN^2)版本的时候都会把dp数组初始化为inf然后再处理边界。但如果忘记了dp[k][0] 0这一条后面dp[i][j]递推时一旦xj就会用到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就在交点两侧你无法保证一定落在AB还是BA的那一边直接取一个点有可能错过最优值。这种“写完二分后顺手把两个边界都算一遍”的思路在处理很多“搜索最优转折点”的题目时都能复用比如珂珂吃香蕉、分割数组的最大值等都可以用这个模板。5.3 面试官最爱的追问这道题在面试里出现频率很高面试官通常会从易到难问三个层次第一个层次K2时你怎么做如果只会线性扫描他会引导你去想动态规划。第二个层次一般化的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。顺着这三个锚点面试时就算紧张也能一步一步接近最优解。反过来讲最怕的就是上来就背那个几行的最优解代码结果被问“为什么从大到小遍历”直接愣住那就露馅了。这道题真正的价值不在于那个最终答案本身而在于它训练了你“如何重新定义状态”的能力。同样一个优化目标你既可以把楼层当作约束、次数当作目标也可以把次数当作约束、楼层当作目标。能在这两种视角之间自由切换你动态规划就算真正入门了。