1. 一道题看懂两种状态定义鸡蛋掉落的本质拆解1.1 题目到底在问什么力扣 887 这道鸡蛋掉落题面其实很短你手里有 K 个鸡蛋面前是一座 N 层的楼存在一个未知的临界楼层 F鸡蛋在 F 层及以下扔下去不会碎在 F 层以上扔下去必碎。问的是在最坏情况下最少需要扔多少次鸡蛋才能保证确定 F 的值第一次读题的人特别容易忽略三个关键词。第一个是最坏情况。题目不是让你赌运气而是要求无论临界楼层 F 落在 0 到 N 之间的哪个位置你的实验次数都必须够用。比如你随便在中间楼层扔了一次运气好可能一次就定位但运气差的时候可能彻底失去判断依据。第二个是保证确定。实验结束之后你要能准确说出 F 等于几而不是大概在那个区域。这要求你的实验方案是一棵完整的决策树每一种可能的碎或不碎序列都要对应到唯一的结论。第三个也是最容易被轻视的鸡蛋碎了就不能再用。没碎的蛋可以反复扔碎掉的蛋直接报废。很多新手把有 K 个鸡蛋理解成我能承受 K 次摔碎或者最多做 K 次实验这两个理解全都是错的。鸡蛋是你手里的资源不是你的失败次数。另外还要注意F 的取值可以是 0意思是第一层扔下去就碎F 也可以是 N意思是 N 层扔下去也不碎。所以 F 一共有 N1 种可能实验方案的本质上就是在 N1 个候选答案里做排除边界条件里 dp[i][0] 这种状态在推导时非常关键。1.2 为什么二分扔鸡蛋的直觉会翻车如果没有鸡蛋数量限制最优策略毫无悬念是二分到中间楼层扔一次碎了处理下半段不碎了处理上半段大约 log2(N) 次就能搞定。但这个直觉在鸡蛋有限的情况下立刻失效。举个最简单的例子你手里只有 1 个蛋。你敢在中间楼层先扔吗如果它碎了你就没有蛋了而临界楼层到底在哪儿你完全不知道游戏直接结束。所以唯一的稳妥做法是从 1 楼开始逐层往上试一楼扔不碎换二楼再不行三楼……直到某一层碎了临界楼层就是这一层的前一层。最坏情况下要试满 N 次少一次都不行。那 2 个蛋呢比 1 个好很多但同样做不了纯二分。常见思路是分段扫描先用第一个蛋隔若干层往上扔确定一个大致区间再用第二个蛋在这个区间里逐层扫。问题立刻变成第一次的间隔取多少才能让最坏情况的总次数最小这个最优间隔不是 10、不是 100而是和 N 的平方根相关的某个值。这里已经能闻到动态规划的味道了——每一次扔蛋都在把原问题拆成两个规模更小的子问题。从这两个极端场景能得出一个重要直觉答案的取值范围是 log2(N)蛋足够多接近纯二分到 N只有一个蛋只能线性扫。蛋越少策略越保守蛋越多越敢跨大步。后面讲到方法二的时候你会发现这个直觉会被一条公式精确地统一起来。1.3 边界情况先摸清一个蛋和无限个蛋在写任何代码之前先把两个退化情况想清楚能省掉大量调试时间。当 K 1 时答案就是 N。因为只能逐层试最坏情况是临界楼层在顶层附近你要从 1 楼一直扔到 N 楼一共 N 次。当 N 1 时答案永远是 1。不管你有几个蛋只有唯一一层楼扔一次就足够区分 F0 和 F1 两种情况。当 K 很大时鸡蛋不再是瓶颈答案趋近于 ceil(log2(N1)) 这个量级。这个性质在方法二的组合数推导里会非常自然地浮现出来。这两个边界不是拿来特判的而是用来验证后续 DP 结果的重要锚点。比如方法一的表格填完之后dp[1][N] 必须等于 Ndp[K][1] 必须等于 1如果对不上说明状态转移或者初始化哪里写错了。2. 方法一二分查找剪枝的动态规划从定义到代码2.1 状态设计与转移方程官方解法一用的是最直觉的正向状态定义dp[i][j] 表示用 i 个鸡蛋去测 j 层楼在最坏情况下最少需要的实验次数。初始化非常直接。dp[1][j] j因为只有一个蛋时只能逐层扫dp[i][0] 0没有楼层就不用测dp[0][j] 也当成 0没有蛋什么都测不了。接下来是核心的转移。假设我们在第 x 层1 x j扔下一个蛋实验结果只有两种第一种鸡蛋碎了。说明临界楼层在 x 层以下也就是 1 到 x-1 层之间同时我们损失了一个蛋手上只剩 i-1 个蛋。子问题的规模是 dp[i-1][x-1]。第二种鸡蛋没碎。说明临界楼层在 x 层以上也就是 x1 到 j 层之间蛋的数量还是 i 个。子问题的规模是 dp[i][j-x]。因为题目要求在最坏情况下最优所以选定 x 之后本次实验的代价是 1 max(dp[i-1][x-1], dp[i][j-x])。我们不知道临界楼层在哪只能按最坏的情况预估。而我们能做的是在所有可能的 x 里挑一个让这个最大值最小的位置当第一个落点。于是转移方程写成dp[i][j] 1 min_{1xj} max(dp[i-1][x-1], dp[i][j-x])如果直接按这个式子写三层循环复杂度是 O(K * N^2)在题面 N 可达一万的场景下必然超时。所以官方解法一的关键动作就是把内层这个枚举 x 找最小值的过程加速而加速的突破口藏在两个子函数的单调性里。2.2 单调性分析为什么可以对 x 做二分内层循环之所以能加速是因为两部分函数有非常漂亮的单调性。先把 dp[i-1][x-1] 记为 A(x)把 dp[i][j-x] 记为 B(x)。A(x) 随 x 增大而单调不减。这个很直观x 越大意味着如果蛋碎了我们要面对的楼层就越多需要的次数只会更多不会更少。B(x) 随 x 增大而单调不增。x 越大意味着如果蛋没碎上方剩下的楼层越少需要的次数自然更少。于是目标函数 g(x) max(A(x), B(x)) 就是一个增函数和一个减函数取最大值。可以想象两条线一条从左下往右上走一条从左上往右下走它们必然会在某个位置附近相交。在交点左边B(x) 占主导在交点右边A(x) 占主导。而 max 取最小值的位置恰恰就在两者最接近的交界处附近。由于 A(x) 和 B(x) 都是离散序列我们不需要精确求交点只要用二分法找到第一个满足 A(x) B(x) 的位置然后把这个位置和它的前一个位置都拿出来算一遍取较小值即可。这一步把内层 O(N) 的枚举降到了 O(log N)。二分的判定条件也很好写看 A(mid) 和 B(mid) 谁大谁小这里的 A、B 都是已经填好的表格值查表是 O(1) 的。整个外层仍然是按鸡蛋数从少到多、楼层数从小到大的顺序填表没有任何跳跃依赖。2.3 完整代码与复杂度给一份可以直接跑的 Python 版本def superEggDrop(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(2, k 1): for j in range(1, n 1): lo, hi 1, j # 找第一个满足 A(x) B(x) 的 x # A(x) dp[i-1][x-1], B(x) dp[i][j-x] while lo hi: mid (lo hi) // 2 if dp[i - 1][mid - 1] dp[i][j - mid]: hi mid else: lo mid 1 x lo best 1 max(dp[i - 1][x - 1], dp[i][j - x]) if x - 1 1: alt 1 max(dp[i - 1][x - 2], dp[i][j - x 1]) best min(best, alt) dp[i][j] best return dp[k][n]几个关键点值得单独说一下。dp[i][j - mid] 里用到的 j - mid 一定小于 j所以它是当前这一行里已经算好的左边格子这个访问顺序是安全的。初学的时候容易担心会不会读到还没填的值其实因为内层循环是从小到大填 j任何右侧下标都不可能先于当前下标被计算。二分找到的是第一个 A B 的位置但最优点可能是它也可能是它的前一位。所以代码里额外算了一次 alt。为什么不检查后一位因为从第一个满足条件的位置往后A 继续增大、B 继续减小max 只会越来越大没有回头的可能。时间复杂度 O(K * N * log N)空间复杂度 O(K * N)。实际跑题目的数据范围完全够用。如果追求空间可以改成滚动数组只保留上一行和当前行但因为要用到当前行的左侧值滚动时注意从右往左更新。2.4 二分边界的细节与滚动数组方法一最大的坑不在 DP 本身而在二分边界的处理。我见过好几个版本最后都差 1原因各不相同。有人把二分的判定写成 dp[i-1][mid] dp[i][j-mid]坐标整体错位一格小数据可能侥幸通过稍微大一点就全错。有人用 while (lo hi) 但更新分支写成了 lo mid导致死循环。还有人二分完直接返回 1 max(...)没检查交点前一位偶尔答案会比正确值大 1。一个非常实用的自查办法是先写一个朴素的 O(K * N^2) 版本用它当标准答案再拿小数据去对拍。朴素版虽然超时但正确性一目了然绝不可能错。对拍几组之后二分的哪个边界写错了立刻就能暴露出来。另外关于滚动数组方法一的状态依赖来自两个方向上一行的任意列以及当前行的左侧列。所以滚动成两行数组完全可行但更新当前行时必须从右往左否则 dp[i][j-x] 读到的可能是这一轮刚算好的新值。这个问题比较隐蔽我在最初自己写的时候也在这里栽过跟头。3. 方法二从次数反向推导一维数组滚动实现3.1 反向状态的定义测多少次能覆盖多少层方法一虽然能过题但状态里既有鸡蛋数又有楼层数转移里还嵌套着 min 和 max思维负担很重。官方解法二换了一个完全不同的视角把问题反过来问如果有 i 个鸡蛋并且只允许做 m 次实验最多能保证覆盖多少层楼把这个最大值记作 dp[i][m]。然后用一个简单的循环不断增大 m直到 dp[K][m] N此时这个 m 就是原题要求的答案。这个反转换掉了一个关键难点。原题的目标是给楼层数求最少次数状态空间里次数的维度是未知的所以必须用 min 去搜索反过来定义之后变成了给次数求最多能覆盖的楼层数次数成了递推的轮数楼层数只是被比较的目标值。你可能会问为什么覆盖这个词用得这么随便因为一次实验能覆盖的层次结构其实是递归的在某个楼层 X 扔蛋如果碎了X 以下的所有楼层都纳入这次实验的覆盖范围如果没碎X 以上的楼层也纳入覆盖。这种上下递归的结构和二叉树非常像而 dp[i][m] 恰恰描述的就是这棵决策树最多能有多少个叶子。3.2 转移方程是怎么推出来的现在来看 dp[i][m] 的递推。假设我们在某一层 X 做第一次实验之后只有两种出路。第一种蛋碎了。X 层以下成为战场但我们只剩 i-1 个蛋、m-1 次机会。根据 dp[i-1][m-1] 的定义X 以下最多能覆盖 dp[i-1][m-1] 层。第二种蛋没碎。X 层以上成为战场我们还有 i 个蛋、m-1 次机会所以 X 以上最多能覆盖 dp[i][m-1] 层。而 X 这一层本身已经被我们扔下去的这一次实验覆盖了——无论它碎不碎我们都能判断出 F 是不是 X。把三块拼起来总覆盖层数 下方的 dp[i-1][m-1] 中间这一层 1 上方的 dp[i][m-1]于是得到极其干净的转移方程dp[i][m] dp[i-1][m-1] dp[i][m-1] 1边界同样是 dp[0][m] 0、dp[i][0] 0。没有蛋或者没有次数能覆盖的楼层数都是 0。为了验证这个递推对不对可以手算几个小值。i1 时dp[1][m] dp[0][m-1] dp[1][m-1] 1 dp[1][m-1] 1所以 dp[1][m] m正好是一个蛋逐层扫 m 次覆盖 m 层。再看 i2、m2 的情况dp[2][2] dp[1][1] dp[2][1] 1 1 1 1 3意思是两个蛋两次实验最多能覆盖 3 层楼。手动验证一下在 2 楼扔第一次碎了就剩 1 楼再扔一次不碎就上 3 楼再扔一次。无论临界楼层是 0、1、2 还是 3两种结果都能确定答案确实覆盖了 3 层。3.3 一维滚动写法与正确性这个递推有一个特别舒服的性质第 m 轮的 dp[i] 只依赖第 m-1 轮的 dp[i-1] 和第 m-1 轮的 dp[i]。换句话说每一轮的状态只和上一轮有关天然适合滚动数组。代码可以写得非常短def superEggDrop(k: int, n: int) - int: dp [0] * (k 1) # dp[i] 表示当前 m 下i 个蛋最多能覆盖的楼层数 m 0 while dp[k] n: m 1 for i in range(k, 0, -1): dp[i] dp[i - 1] dp[i] 1 return m必须强调为什么内层循环要从 k 往 1 倒着走。更新 dp[i] 的时候等式右边的 dp[i-1] 必须还是上一轮 m-1 次实验的结果而不是这一轮刚更新过的值。如果从 1 往 k 正着走更新 dp[i] 时 dp[i-1] 已经被改成了新值递推关系就被破坏了。倒着走能保证右边的 dp[i-1] 永远是旧值。这个手法在背包类问题里极其常见刷过 0-1 背包的人一眼就能认出来。本质上是因为状态依赖方向交错必须用遍历顺序来控制依赖的时效性。整个核心逻辑就是一个 while 加一个 for面试手写毫无压力。循环最多不会超过 N 轮因为 K1 时答案正好是 N所以最坏时间复杂度是 O(K * N)空间复杂度直接降到 O(K)。实际运行中 dp[K] 增长非常快通常远到不了 N 轮就满足了。3.4 顺带挖出组合数规律如果把这个递推多展开几步会发现一个很有趣的现象。dp[1][m] m这是一次项。dp[2][m] m(m1)/2变成二次项。dp[3][m] 继续展开会出现三次项。事实上存在闭式解dp[i][m] C(m,1) C(m,2) ... C(m,i)验证方法很简单利用组合恒等式 C(m,t) C(m-1,t-1) C(m-1,t)代入递推方程两边正好能对上。这个公式能带来两个直观结论。当 i 足够大也就是 i m 时dp[i][m] 2^m - 1意味着鸡蛋足够多时答案接近 log2(N1)完全回到纯二分的结论。当 i 很小比如 i1 时dp[1][m] m答案退化成 N逐层扫描的结论。两个极端被一条公式统一起来这是我当时推出来之后觉得最畅快的时刻。刷题网站上很多讨论帖会用杨辉三角叠加来形容这个递推确实是同一件事。4. 两种官方解法的对比以及我踩过的几个坑4.1 两版解法成本对比把两种方法放在一起差别会非常直观对比维度方法一正向 DP 二分方法二反向次数 DP状态定义dp[i][j]i 个蛋测 j 层需要的最少次数dp[i][m]i 个蛋 m 次最多覆盖的层数转移方程1 min max 嵌套dp[i-1][m-1] dp[i][m-1] 1时间复杂度O(K * N * log N)O(K * ans)ans 是答案不超过 N空间复杂度O(K * N)滚动可降为 O(N)O(K)实现难度中等二分边界容易写错简单十几行搞定思维路径顺着题目正向建模反向建模先给次数再猜楼层如果只看刷题通过率方法二几乎是完美答案代码短、常数小、不需要处理二分边界。但方法一也绝不是没用它背后的枚举决策点 利用单调性优化的思想在很多其他题目里会反复出现而且某些变种题一旦要求输出具体扔蛋策略正向状态反而更容易扩展。我个人在准备面试时两个方法都要求自己能独立写出来。方法一是底线面试官如果只问思路方法一的推导足够展现基本功方法二是亮点能直接把最优雅的解法甩出来通常会让面试环节轻松不少。4.2 刷题时最常见的几个错我身边刷这道题的人翻车的姿势高度集中在下面几类这里一次性列出来。第一类把鸡蛋数量当成允许摔碎的次数。这是语义理解错。K 个蛋不是 K 条命而是 K 次不容浪费的实验资源而且没碎的蛋能反复利用这两件事完全不是一回事。第二类忘记临界楼层可以是 0。很多人默认 F 在 1 到 N 之间推导答案的时候少算了 F0 这个候选最后对不上。记住 F 有 N1 种可能dp[i][0] 这个边界状态的存在感非常高。第三类方法一的二分边界写错。前面已经说过建议先写朴素版对拍。朴素版超时归超时正确性一目了然拿它当基准测几组小数据二分哪里写错了立刻能定位。第四类方法二一维滚动写成正向更新。把 for i in range(k, 0, -1) 写成 range(1, k1)小数据看起来还行稍微大一点就乱套。原因就是 dp[i-1] 被提前更新成新值了。第五类while 终止条件写成 dp[k] n。我们要找的是 dp[k] 第一次大于等于 n 的最小 m写成 会多跑一轮答案正好多 1。4.3 面试现场的一些参考思路如果这道题出现在面试里我推荐的破题顺序是这样的。先把边界讲清楚一个蛋必须逐层扫答案是 N蛋足够多接近二分答案是 log2(N) 量级。这两句话能立刻证明你理解问题本质而不是在背模板。然后从两个蛋开始推。两个蛋怎么选第一次扔的楼层你很快能写出 dp[i][j] 1 min max 的式子这是每个人都能到达的一步先落地再优化。接下来有两个分支。如果面试官问能不能再优化你可以提方法一的单调性二分如果你想做得更漂亮可以直接给出方法二的反向定义十几行代码写完再解释为什么倒着更新一维数组。大多数情况下面试官对反向状态定义的兴趣会比二分细节高得多因为这才是真正体现思维切换的地方。我在准备这道题时的体会是方法二才是真正理解这道题的门。方法一能让你顺着题目的意思硬做方法二能让你看到换一个状态难题变简单题的快乐。刷过这道之后我对所有最小化最大步数类型的题都有了新的敏感度——先想想能不能把次数和目标交换一下位置往往会有奇效。最后分享一个小技巧把反向 DP 的递推和组合数公式自己从头推一遍而不是只看题解。推完一遍之后这道题基本就长在脑子里了就算下次忘了代码也能现场把递推重新导出来。
的KM算法BFS模板：从顶标到增广全解析)
