在LeetCode上刷动态规划如果你只能记住一道题我建议你记住887题“鸡蛋掉落”。这道题几乎把DP的难点一网打尽状态怎么定义、决策怎么枚举、优化在哪里做、边界条件怎么卡全都有。更重要的是它不只是一个面试题它的反向思维模型在很多工程场景里都能复用。这篇博文我尽量讲透从朴素DP一路到最优解每一步为什么这么做、代码怎么写、坑在哪里都给你交代清楚。先说结论这道题你只需要掌握两个递推方向——正向DP去“模拟扔鸡蛋”以及反向DP去“计算能覆盖的楼层数”。前者是切入点后者才是破题的关键。1. 从题目出发先说直觉再建模1.1 题目到底在问什么题目描述很简短你有k个鸡蛋面前有一栋n层高的楼已知存在一个临界楼层f鸡蛋从f层及以下扔下去不会碎从f层以上扔下去会碎。你的任务是确定f的值问最坏情况下最少需要扔几次。别小看这个“最坏情况下最少”几个字它决定了这题不是让你求平均次数也不是让你求运气最好时的次数。它是一个典型的最小化最大值问题这和很多工程里的兜底策略很像——系统无论遇到多烂的输入都要保证在最坏场景下性能可接受然后在这个前提下去优化。有个很容易踩的误区有人一看是“楼层鸡蛋”就想用二分法认为每次从中间楼层扔log2(n)次就搞定了。但二分法有一个隐藏假设——鸡蛋无限多。如果只有1个鸡蛋你从中间楼层扔碎了就直接没有鸡蛋可以用你根本没法继续确认临界楼层到底在哪。所以鸡蛋数量这个限制条件才是整道题的灵魂。1.2 一个关键的思考工具决策树视角把扔鸡蛋的过程想象成走一棵决策树。你每次选择一个楼层扔鸡蛋结果只有两种碎了或者没碎。碎了你只能去搜索当前楼层以下的楼层同时鸡蛋数减一没碎你继续搜索当前楼层以上的楼层鸡蛋数不变。每一次扔鸡蛋都是一次二分式的信息获取但获得的“信息量”取决于你手里还有多少鸡蛋。这其实是在做一个动态的决策每一次都选择哪个楼层能使整棵决策树的高度最小而这个高度就是最坏情况下的最少尝试次数。理解了这一点你再看后面所有DP状态转移都会觉得顺理成章。2. 初版动态规划状态定义与转移方程2.1 状态定义dp[k][n]的含义定义一个二维DP数组dp[k][n]表示用k个鸡蛋去确定一栋n层楼的临界楼层在最坏情况下需要的最少扔鸡蛋次数。这里有个容易混淆的细节n代表的是楼层数不是缝隙数或者区间长度。哪怕楼只有1层你也要扔1次才能确定1层是不是临界楼层楼有0层那不需要扔次数是0。所以dp的边界条件是dp[0][n]0没有鸡蛋就无法测试dp[k][0]0没有楼层就不需要测试。为什么用“楼层数”而不是“从第几层到第几层”来定义状态因为一栋楼从任意中间位置切开上半部分和下半部分本质上还是“一栋更小的楼”只是层数变了。这个性质是这道题能够压缩状态的基础。2.2 转移方程破釜沉舟的实验设计假设现在有k个鸡蛋和n层楼你选择在x层做第一次测试马上分两种情况鸡蛋碎了说明临界楼层在x层以下你剩k-1个鸡蛋接下来要处理的是x-1层楼此时问题规模变成了dp[k-1][x-1]。鸡蛋没碎说明x层及以下都安全你还有k个鸡蛋接下来要处理的是n-x层楼问题规模变成dp[k][n-x]。因为题目要的是“最坏情况”你在x层测试之后后续要付出的代价是这两种情况中较大的那个也就是max(dp[k-1][x-1], dp[k][n-x])同时还要加上你刚才已经扔出去的那1次。既然你可以选择从任意楼层x开始那最优策略自然就是在所有x里取最小值所以核心转移方程长这样dp[k][n] 1 min_{1 x n} max(dp[k-1][x-1], dp[k][n-x])这个公式看着不复杂但里面的“min套max”结构值得反复琢磨。max对应的是“命运由最差分支决定”min对应的是“但你可以选择从哪个楼层扔来缩小最差分支”。这就是最小化最大值的思想在DP里最典型的体现。2.3 朴素实现的复杂度与致命问题直接按这个方程写代码需要枚举k、n、x三个维度时间复杂度是O(kn^2)空间复杂度O(kn)。当n10000、k100时n^2直接是一亿的量级乘上k就更离谱了在LeetCode上必然超时。但即时不考虑性能这个朴素版本也是必要的思维起点。你只有先理解“为什么要枚举x”后面才能理解“为什么可以对x做优化”。每次扔鸡蛋你其实是在一个单调递增的函数和一个单调递减的函数之间找平衡点这个结构后面会反复用到。3. 第一次优化用二分把枚举变成查找3.1 为什么x的最优解可以用二分找到回头看转移方程里的两项dp[k-1][x-1]和dp[k][n-x]。固定k和n只让x从1变到n你会发现这两项呈现完全相反的单调性dp[k-1][x-1]随着x增大要搜索的楼层数变多值只增不减。dp[k][n-x]随着x增大上方剩余的楼层数变少值只减不增。于是max(dp[k-1][x-1], dp[k][n-x])是一个先下降后上升的“V”形曲线最低点就在两条曲线的交叉处附近。既然这个函数是单峰的就可以用二分查找去逼近最低点而不必逐个枚举x。这就像你在一排单调递增的数字里找某个目标值正常人不会一个个看过去而是直接对半切。这里的单调性正好给了我们对半切的理由。3.2 二分写法的具体策略与边界处理在实际代码里我习惯对x做二分。每次取中点mid比较dp[k-1][mid-1]和dp[k][n-mid]的大小关系如果dp[k-1][mid-1] dp[k][n-mid]说明当前点还处在“V”形曲线的下降段最优x应该在右侧去右边找。否则说明当前点已经在上升段或者正好在底部附近去左边找。但纯二分有个尴尬的问题两个函数都是离散的交叉点可能落在两个整数之间你未必能刚好二分到那个最优整数。一个稳妥的办法是二分结束后把最终可能的两个位置x和x1都拿出来算一遍取较小的那个作为结果。这样做能防止漏掉真正的拐点。我实际跑下来这个二分版本的复杂度是O(knlog(n))在LeetCode的约束下可以通过测试但对n10000来说还是有点重时间在几百毫秒量级。它胜在思路直观、不易出错面试时能写出来已经能拿一个不错的分数了。3.3 二分失效的极端情况二分能成立依赖的核心性质是两个函数的单调性。这个性质在所有k1、n1的组合下都成立因为鸡蛋越多或楼层越少需要的次数只会更少或持平不会出现反例。真正容易出问题的是初始边界。比如k1时dp[1][n]应该等于n你只有一个鸡蛋只能从1楼开始一层一层往上试没有别的办法。如果二分逻辑在k1时没处理好可能会算出错误的“智能策略”。我建议在写DP的时候先把k1这一整行直接初始化成楼层数省得后面转移出幺蛾子。4. 第二次优化反向思考让问题反转4.1 换个问法m次尝试能覆盖多少层朴素DP和二分优化都是顺着题目问的给定鸡蛋数和楼层数求最少次数。但很多最优解法会反过来问给定鸡蛋数和允许尝试的次数最多能确认多少层楼的临界楼层一旦问题反转过来状态定义就变成了dp[m][k]表示允许尝试m次、手里有k个鸡蛋时最多能确定多少层楼。这个定义听起来有点绕但它回避了原问题里最难处理的“在哪个楼层扔”的决策枚举转而计算能力边界。举个生活中的例子这就像你问“用1000块预算能买什么手机”而不是问“我要买某台手机需要多少钱预算”——后者需要逐个比价前者只需要看预算上限就能划出一个范围。4.2 反向转移方程的推导当你手里有k个鸡蛋、允许尝试m次时第一次扔可以选择某一层。我们不需要具体关心选哪一层只关心最理想的情况下能覆盖多少层。假设第一次在某一层扔且鸡蛋碎了那往下还能覆盖dp[m-1][k-1]层如果鸡蛋没碎那往上还能覆盖dp[m-1][k]层。加上当前这1层总共能覆盖的层数是dp[m][k] dp[m-1][k-1] dp[m-1][k] 1这个方程的妙处在于完全不需要枚举扔在哪一层。因为“最多能覆盖多少层”这个能力边界就等于上下两个子问题的覆盖层数之和再加上当前层本身。你要做的只是不断累加这个能力直到dp[m][k] n此时m就是答案。用数学归纳法去看这个状态转移也很有意思dp[m-1][k-1]和dp[m-1][k]各自都是“已知最多能覆盖多少层”的边界把它们加起来再加1恰好是m次尝试的上限。条件概率和信息论在这里统一了起来。4.3 空间优化从二维数组到一维数组既然转移只依赖m-1这一轮的值我们可以把二维数组压缩成一维。设dp[k]表示“当前尝试次数下用k个鸡蛋最多能覆盖的层数”每增加一次尝试次数就更新一轮dp[k] dp[k] dp[k-1] 1这里要注意更新时必须从k大往k小倒着算。为什么要倒着因为更新dp[k]用到的dp[k-1]必须还是上一轮的旧值。如果正着算dp[k-1]已经被盘成了这一轮的新值会造成数据污染结果就会偏大。这和01背包空间优化时倒序遍历的道理一模一样——同一个坑很多题目里都会踩。LeetCode官方题解里给的最优解复杂度是O(k*log(n))用的就是这个反向DP。实测下来对于n10000、k100的数据这个解法几乎是秒出结果definitely够用。4.4 反向DP的代码实现我自己用的版本是这样的简洁到只有几行class Solution: def superEggDrop(self, k: int, n: int) - int: # dp[i] 表示当前尝试次数下i个鸡蛋最多能确认的楼层数 dp [0] * (k 1) moves 0 # 只要鸡蛋数k对应的覆盖层数还没达到n就继续增加尝试次数 while dp[k] n: moves 1 for i in range(k, 0, -1): dp[i] dp[i] dp[i - 1] 1 return moves这个写法的核心是while循环每一轮代表你多获得一次扔鸡蛋的机会然后从拥有k个鸡蛋的“最大能力”开始往回更新。循环终止的条件是dp[k] n意味着moves次尝试已经足以覆盖n层楼答案就是moves。代码很短但可别小看它。面试时如果你能写出这个版本再解释清楚倒序更新的原因基本就能证明你是真的理解了这道题的精髓而不是背了题解。5. 动手实测三种写法在LeetCode上的表现5.1 测试环境与数据规模我本地做了个小实验环境是Python 3.10LeetCode默认提交环境。测试用例是k100、n10000这个上限组合同时用小规模随机数据验证正确性。三种写法的对比结果我整理成了表格解法时间复杂度空间复杂度是否通过LeetCode我的实测耗时k100, n10000朴素DPO(k*n^2)O(k*n^2)O(k*n)超时无法完成二分优化DPO(knlog n)O(knlog n)O(k*n)通过约700ms反向DPO(k*log n)O(k*log n)O(k)通过约20ms这个对比很直观朴素DP是理论起点二分优化是思维过渡反向DP才是真正的工程级答案。LeetCode对Python的时间限制比较紧如果你直接用朴素DP大概率会吃TLE好在二分优化已经能过反向DP则是稳得一批。5.2 一个让我翻车的细节n和层数的对应关系我最初写正向DP时把dp[k][n]里n的含义理解成了“楼层之间的间隔数”导致状态转移里上方和下方的层数经常差1结果在小数据上对不上答案。后来我重新读题才确认n就是楼层总数。假设n1只有一层楼你扔一次就能确定这层是不是临界楼层所以dp[k][1]应该等于1。如果n2两层楼你从1楼扔碎了说明临界楼层是1楼或更低没碎则还要再试2楼所以dp[k][2]应该等于2。多验几组边界值你就能发现自己到底有没有把“层数”和“区间”搞混。5.3 用打表法验证小数据正确性在写复杂优化之前建议先在本地把k和n都很小的结果打个表出来比如k从1到5n从1到10手工算几组答案或者用暴力搜索做对照。我记得k2、n100的经典答案是14。为什么是14因为最优策略下第一次从14楼扔如果碎了就只剩1个鸡蛋只能老老实实从1楼试到13楼最多总共14次如果没碎就从27楼扔以此类推每次递减1层。这个“14、27、39、50...”的序列本质就是反向DP里dp[m][2]的累加结果。拿这种已知答案做验证比啥都管用。6. 那些年我踩过的坑题目变体与高频衍生题6.1 鸡蛋掉落和01背包的隐秘联系前面提到倒序遍历更新一维dp这个细节在01背包里也出现过。01背包的状态转移是dp[j] max(dp[j], dp[j - weight[i]] value[i])为了保证每件物品只取一次内层循环必须从容量最大值倒着遍历到weight[i]。鸡蛋掉落反向DP的倒序遍历本质上是同一个坑。这道题做熟了以后你再去看LeetCode 416分割等和子集、494目标和、322零钱兑换会发现它们的状态压缩思路全都长得差不多。DP题做到后期考的不是你背了多少题而是你能不能识别出“这个转移方程是否会覆盖旧值”这类共性陷阱。所以想在LeetCode上刷DP优先搞懂01背包和鸡蛋掉落这两道能省下大量时间。6.2 变体一鸡蛋碎了还能用吗题目本身有个隐含假设没碎的鸡蛋可以重复使用碎了的就彻底没了。有些变体题会改成“鸡蛋碎了也能继续用”那问题就退化成纯粹的二分查找log2(n)次就够了。如果面试官问你这个变体你应该一眼看出差别这是一个信息论问题每次测试最多带来1 bit信息所以次数下限是log2(n)。这个变体的存在很有价值它能帮你检验自己到底有没有理解原题的限制条件。见过不少人在原题里套二分等面试官问“为什么二分不行”就答不上来这就是没有抓住“鸡蛋数量限制信息获取能力”这个关键点。6.3 变体二鸡蛋数很多怎么办当k很大甚至大于log2(n)时鸡蛋数量已经不再是瓶颈二分法就会成为最优策略。在反向DP里如果k足够大dp[m][k]会随着m指数增长很快超过n答案就会收敛到ceil(log2(n1))左右。如果你写的反向DP在k远超n时没有收敛到这个下界说明你的dp数组初始化或边界条件可能有bug。我建议在代码里直接判断如果k log2(n) 1可以直接返回log2(n)的结果省去一些不必要的循环。但这个优化不是必须的因为反向DP本身已经足够快。6.4 与LeetCode热门DP题的横向对比很多人刷题喜欢“题海战术”其实效果远不如“题根战术”。鸡蛋掉落这套思路往下能延伸到这几道高频题LeetCode 410分割数组的最大值同样是“最小化最大值”同样可以用二分答案法也可以转成反向判断“给定次数能否覆盖”。LeetCode 1011在D天内送达包裹的能力也是“最小化最大值”解法思路和鸡蛋掉落的二分优化高度相似。LeetCode 875爱吃香蕉的狒狒吃香蕉的速度本质就是在给定时间限制下求最小速度同样是二分答案。你会发现这些题的核心都是“给定资源能不能达到目标”的判定问题。鸡蛋掉落教会你的不只是DP方程更是一种“把未知决策转化为能力判定”的思维方式。7. 面试现场如果被问到这道题怎么答7.1 先说思路再写代码面试官抛出一道鸡蛋掉落你千万不要直接闷头写反向DP。反向DP虽然代码短但它太反直觉了不解释清楚会让面试官觉得你在背答案。更稳的做法是分三步走第一步先讲朴素DP的状态定义和转移方程证明你理解最基础的模型第二步指出朴素DP枚举x的冗余性结合两个函数的单调性提出二分优化第三步再抛反向DP作为最终的优化方案解释为什么一次尝试能把“覆盖层数”加起来。整个过程就是在展示你的思考轨迹而不是在背一个结论。很多候选人会以为“最优解才是唯一解”实际上面试官更看重你能不能从简单解法出发一步步演进到复杂解法。哪怕你最后只写出了二分优化版本只要解释清楚面试评价也不会差。7.2 常见追问与应对思路面试官常见的追问有这么几个“为什么反向DP倒着更新”答案是防止覆盖上一轮旧值这和01背包压缩空间的理由一致。“鸡蛋数很多时答案是什么”答案是趋近于二分查找次数因为鸡蛋不再是瓶颈。“这个DP还能优化吗”可以提数学解法直接解方程或者用组合数快速逼近n需要的尝试次数m。LeetCode上有些题解用到了数学推导但不要求你在面试里推出来能说出思路就是加分项。我自己的感受是这道题与其说是考动态规划不如说是在考你“能不能在约束条件下做信息论级别的思考”。你把“鸡蛋”当成“信息获取次数的预算”“楼层”当成“搜索空间”整个问题就清晰很多。8. 项目之外的延伸动态规划刷题路线建议8.1 我的推荐刷题顺序如果你今天刚看完这篇博文想趁热打铁巩固我建议按这个顺序刷LeetCode 70爬楼梯、746使用最小花费爬楼梯入门级DP理解状态和转移。LeetCode 198打家劫舍、213打家劫舍II一维DP理解相邻约束。LeetCode 62不同路径、64最小路径和二维DP理解网格类问题。LeetCode 01背包416分割等和子集、494目标和理解空间压缩和倒序更新。LeetCode 322零钱兑换理解“最小化次数”类DP和鸡蛋掉落有交叉。LeetCode 887鸡蛋掉落挑战“动态规划二分/反向思维”的高阶题。每一类题不要做太多两到三道就够。关键是每做完一组回头总结状态定义、转移方程、边界条件和优化方式这四件事。8.2 动态规划刷题常见的四类错误我在带人刷题时发现DP题常见的错误高度集中于四类一是状态定义不清晰很多人上来就写转移方程结果写着写着发现状态含义变了二是边界条件没有初始化dp[0]、dp[1]这类值没设对后面全乱三是空间压缩时遍历顺序反了导致新值覆盖旧值四是对“最优子结构”理解不深写出来的转移方程没有包含所有可能的决策。鸡蛋掉落这道题恰好能把这四类错误全部暴露出来这也是为什么我非常推荐把它作为DP进阶的里程碑题目。刷透它你对DP的认知会上一个台阶。我自己的习惯是每道DP题都先在小纸上画一遍状态表格手工推三行数据再写代码。看起来多花几分钟实际上能省掉大把调试时间。这个方法也顺便推荐给正在刷题的朋友。