企业官网建设流程全解析

1. 一道题看懂两种状态定义：鸡蛋掉落的本质拆解

1.1 题目到底在问什么

力扣 887 这道"鸡蛋掉落"，题面其实很短：你手里有 K 个鸡蛋，面前是一座 N 层的楼，存在一个未知的临界楼层 F，鸡蛋在 F 层及以下扔下去不会碎，在 F 层以上扔下去必碎。问的是：在最坏情况下，最少需要扔多少次鸡蛋，才能保证确定 F 的值？

第一次读题的人，特别容易忽略三个关键词。

第一个是"最坏情况"。题目不是让你赌运气，而是要求无论临界楼层 F 落在 0 到 N 之间的哪个位置，你的实验次数都必须够用。比如你随便在中间楼层扔了一次，运气好可能一次就定位，但运气差的时候可能彻底失去判断依据。

第二个是"保证确定"。实验结束之后，你要能准确说出 F 等于几，而不是"大概在那个区域"。这要求你的实验方案是一棵完整的决策树，每一种可能的碎或不碎序列，都要对应到唯一的结论。

第三个也是最容易被轻视的："鸡蛋碎了就不能再用"。没碎的蛋可以反复扔，碎掉的蛋直接报废。很多新手把"有 K 个鸡蛋"理解成"我能承受 K 次摔碎"或者"最多做 K 次实验"，这两个理解全都是错的。鸡蛋是你手里的资源，不是你的失败次数。

另外还要注意，F 的取值可以是 0，意思是第一层扔下去就碎；F 也可以是 N，意思是 N 层扔下去也不碎。所以 F 一共有 N+1 种可能，实验方案的本质上就是在 N+1 个候选答案里做排除，边界条件里 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。不管你有几个蛋，只有唯一一层楼，扔一次就足够区分 F=0 和 F=1 两种情况。

当 K 很大时，鸡蛋不再是瓶颈，答案趋近于 ceil(log2(N+1)) 这个量级。这个性质在方法二的组合数推导里会非常自然地浮现出来。

这两个边界不是拿来"特判"的，而是用来验证后续 DP 结果的重要锚点。比如方法一的表格填完之后，dp[1][N] 必须等于 N，dp[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 层以上，也就是 x+1 到 j 层之间，蛋的数量还是 i 个。子问题的规模是 dp[i][j-x]。

因为题目要求在"最坏情况"下最优，所以选定 x 之后，本次实验的代价是 1 + max(dp[i-1][x-1], dp[i][j-x])。我们不知道临界楼层在哪，只能按最坏的情况预估。而我们能做的，是在所有可能的 x 里，挑一个让这个最大值最小的位置当第一个落点。

于是转移方程写成：

dp[i][j] = 1 + min_{1<=x<=j} 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。

为了验证这个递推对不对，可以手算几个小值。i=1 时，dp[1][m] = dp[0][m-1] + dp[1][m-1] + 1 = dp[1][m-1] + 1，所以 dp[1][m] = m，正好是"一个蛋逐层扫 m 次覆盖 m 层"。

再看 i=2、m=2 的情况：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 轮，因为 K=1 时答案正好是 N，所以最坏时间复杂度是 O(K * N)，空间复杂度直接降到 O(K)。实际运行中 dp[K] 增长非常快，通常远到不了 N 轮就满足了。

3.4 顺带挖出组合数规律

如果把这个递推多展开几步，会发现一个很有趣的现象。

dp[1][m] = m，这是一次项。dp[2][m] = m(m+1)/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(N+1)，完全回到纯二分的结论。当 i 很小，比如 i=1 时，dp[1][m] = m，答案退化成 N，逐层扫描的结论。两个极端被一条公式统一起来，这是我当时推出来之后觉得最畅快的时刻。刷题网站上很多讨论帖会用"杨辉三角叠加"来形容这个递推，确实是同一件事。

4. 两种官方解法的对比，以及我踩过的几个坑

4.1 两版解法成本对比

把两种方法放在一起，差别会非常直观：

如果只看刷题通过率，方法二几乎是完美答案：代码短、常数小、不需要处理二分边界。但方法一也绝不是没用，它背后的"枚举决策点 + 利用单调性优化"的思想在很多其他题目里会反复出现，而且某些变种题一旦要求输出具体扔蛋策略，正向状态反而更容易扩展。

我个人在准备面试时，两个方法都要求自己能独立写出来。方法一是底线，面试官如果只问思路，方法一的推导足够展现基本功；方法二是亮点，能直接把最优雅的解法甩出来，通常会让面试环节轻松不少。

4.2 刷题时最常见的几个错

我身边刷这道题的人，翻车的姿势高度集中在下面几类，这里一次性列出来。

第一类：把"鸡蛋数量"当成"允许摔碎的次数"。这是语义理解错。K 个蛋不是 K 条命，而是 K 次不容浪费的实验资源，而且没碎的蛋能反复利用，这两件事完全不是一回事。

第二类：忘记临界楼层可以是 0。很多人默认 F 在 1 到 N 之间，推导答案的时候少算了 F=0 这个候选，最后对不上。记住 F 有 N+1 种可能，dp[i][0] 这个边界状态的存在感非常高。

第三类：方法一的二分边界写错。前面已经说过，建议先写朴素版对拍。朴素版超时归超时，正确性一目了然，拿它当基准测几组小数据，二分哪里写错了立刻能定位。

第四类：方法二一维滚动写成正向更新。把 for i in range(k, 0, -1) 写成 range(1, k+1)，小数据看起来还行，稍微大一点就乱套。原因就是 dp[i-1] 被提前更新成新值了。

第五类：while 终止条件写成 dp[k] <= n。我们要找的是 dp[k] 第一次大于等于 n 的最小 m，写成 <= 会多跑一轮，答案正好多 1。

4.3 面试现场的一些参考思路

如果这道题出现在面试里，我推荐的破题顺序是这样的。

先把边界讲清楚：一个蛋必须逐层扫，答案是 N；蛋足够多接近二分，答案是 log2(N) 量级。这两句话能立刻证明你理解问题本质，而不是在背模板。

然后从两个蛋开始推。两个蛋怎么选第一次扔的楼层？你很快能写出 dp[i][j] = 1 + min max 的式子，这是每个人都能到达的一步，先落地再优化。

接下来有两个分支。如果面试官问能不能再优化，你可以提方法一的单调性二分；如果你想做得更漂亮，可以直接给出方法二的反向定义，十几行代码写完，再解释为什么倒着更新一维数组。大多数情况下，面试官对反向状态定义的兴趣会比二分细节高得多，因为这才是真正体现思维切换的地方。

我在准备这道题时的体会是：方法二才是真正理解这道题的门。方法一能让你顺着题目的意思硬做，方法二能让你看到"换一个状态，难题变简单题"的快乐。刷过这道之后，我对所有"最小化最大步数"类型的题都有了新的敏感度——先想想能不能把"次数"和"目标"交换一下位置，往往会有奇效。

最后分享一个小技巧：把反向 DP 的递推和组合数公式自己从头推一遍，而不是只看题解。推完一遍之后，这道题基本就长在脑子里了，就算下次忘了代码，也能现场把递推重新导出来。