今天要聊一个很经典的算法问题，若干层楼，若干个鸡蛋，让你算出最少的尝试次数，找到鸡蛋恰好摔不碎的那层楼。国内大厂以及谷歌脸书面试都经常考察这道题，只不过他们觉得扔鸡蛋太浪费，改成扔杯子，扔破碗什么的。
具体的问题等会再说，但是这道题的解法技巧很多，光动态规划就好几种效率不同的思路，最后还有一种极其高效数学解法。秉承咱们号一贯的作风，拒绝奇技淫巧，拒绝过于诡异的技巧，因为这些技巧无法举一反三，学了不太划算。
下面就来用我们一直强调的动态规划通用思路来研究一下这道题。
887. 鸡蛋掉落
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
示例 1：
输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例 2：
示例 3：
提示：
1 <= K <= 1001 <= N <= 10000
一、解析题目
题目是这样：你面前有一栋从 1 到N共N层的楼，然后给你K个鸡蛋（K至少为 1）。现在确定这栋楼存在楼层0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于F的楼层都会碎，低于F的楼层都不会碎）。现在问你，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层F呢？
PS：F 可以为 0，比如说鸡蛋在 1 层都能摔碎，那么 F = 0。
也就是让你找摔不碎鸡蛋的最高楼层F，但什么叫「最坏情况」下「至少」要扔几次呢？我们分别举个例子就明白了。
比方说现在先不管鸡蛋个数的限制，有 7 层楼，你怎么去找鸡蛋恰好摔碎的那层楼？
最原始的方式就是线性扫描：我先在 1 楼扔一下，没碎，我再去 2 楼扔一下，没碎，我再去 3 楼……
以这种策略，最坏情况应该就是我试到第 7 层鸡蛋也没碎（F = 7），也就是我扔了 7 次鸡蛋。
现在你应该理解什么叫做「最坏情况」下了，鸡蛋破碎一定发生在搜索区间穷尽时，不会说你在第 1 层摔一下鸡蛋就碎了，这是你运气好，不是最坏情况。
现在再来理解一下什么叫「至少」要扔几次。依然不考虑鸡蛋个数限制，同样是 7 层楼，我们可以优化策略。
最好的策略是使用二分查找思路，我先去第(1 + 7) / 2 = 4层扔一下：
如果碎了说明F小于 4，我就去第(1 + 3) / 2 = 2层试……
如果没碎说明F大于等于 4，我就去第(5 + 7) / 2 = 6层试……
以这种策略，最坏情况应该是试到第 7 层鸡蛋还没碎（F = 7），或者鸡蛋一直碎到第 1 层（F = 0）。然而无论那种最坏情况，只需要试log7向上取整等于 3 次，比刚才的 7 次要少，这就是所谓的至少要扔几次。
PS：这有点像 Big O 表示法计算算法的复杂度。
实际上，如果不限制鸡蛋个数的话，二分思路显然可以得到最少尝试的次数，但问题是，现在给你了鸡蛋个数的限制K，直接使用二分思路就不行了。
比如说只给你 1 个鸡蛋，7 层楼，你敢用二分吗？你直接去第 4 层扔一下，如果鸡蛋没碎还好，但如果碎了你就没有鸡蛋继续测试了，无法确定鸡蛋恰好摔不碎的楼层F了。这种情况下只能用线性扫描的方法，算法返回结果应该是 7。
有的读者也许会有这种想法：二分查找排除楼层的速度无疑是最快的，那干脆先用二分查找，等到只剩 1 个鸡蛋的时候再执行线性扫描，这样得到的结果是不是就是最少的扔鸡蛋次数呢？
很遗憾，并不是，比如说把楼层变高一些，100 层，给你 2 个鸡蛋，你在 50 层扔一下，碎了，那就只能线性扫描 1～49 层了，最坏情况下要扔 50 次。
如果不要「二分」，变成「五分」「十分」都会大幅减少最坏情况下的尝试次数。比方说第一个鸡蛋每隔十层楼扔，在哪里碎了第二个鸡蛋一个个线性扫描，总共不会超过 20 次。
最优解其实是 14 次。最优策略非常多，而且并没有什么规律可言。
说了这么多废话，就是确保大家理解了题目的意思，而且认识到这个题目确实复杂，就连我们手算都不容易， 如何用算法解决呢？
二、思路分析
对动态规划问题，直接套我们以前多次强调的框架即可：这个问题有什么「状态」，有什么「选择」，然后穷举。
「状态」很明显，就是当前拥有的鸡蛋数K和需要测试的楼层数N。随着测试的进行，鸡蛋个数可能减少，楼层的搜索范围会减小，这就是状态的变化。
「选择」其实就是去选择哪层楼扔鸡蛋。回顾刚才的线性扫描和二分思路，二分查找每次选择到楼层区间的中间去扔鸡蛋，而线性扫描选择一层层向上测试。不同的选择会造成状态的转移。
现在明确了「状态」和「选择」，动态规划的基本思路就形成了：肯定是个二维的dp数组或者带有两个状态参数的dp函数来表示状态转移；外加一个 for 循环来遍历所有选择，择最优的选择更新结果 ：
# 当前状态为 (K 个鸡蛋，N 层楼)# 返回这个状态下的最优结果def dp(K, N):int resfor 1 <= i <= N:res = min(res, 这次在第 i 层楼扔鸡蛋)return res
这段伪码还没有展示递归和状态转移，不过大致的算法框架已经完成了。
我们在第i层楼扔了鸡蛋之后，可能出现两种情况：鸡蛋碎了，鸡蛋没碎。注意，这时候状态转移就来了：
如果鸡蛋碎了，那么鸡蛋的个数K应该减一，搜索的楼层区间应该从[1..N]变为[1..i-1]共i-1层楼；
如果鸡蛋没碎，那么鸡蛋的个数K不变，搜索的楼层区间应该从 [1..N]变为[i+1..N]共N-i层楼。
PS：细心的读者可能会问，在第i层楼扔鸡蛋如果没碎，楼层的搜索区间缩小至上面的楼层，是不是应该包含第i层楼呀？不必，因为已经包含了。开头说了 F 是可以等于 0 的，向上递归后，第i层楼其实就相当于第 0 层，可以被取到，所以说并没有错误。
因为我们要求的是最坏情况下扔鸡蛋的次数，所以鸡蛋在第i层楼碎没碎，取决于那种情况的结果更大：
def dp(K, N):
for 1 <= i <= N:
# 最坏情况下的最少扔鸡蛋次数
res = min(res,
max(
dp(K - 1, i - 1), # 碎
dp(K, N - i) # 没碎
) + 1 # 在第 i 楼扔了一次
)
return res
递归的 base case 很容易理解：当楼层数N等于 0 时，显然不需要扔鸡蛋；当鸡蛋数K为 1 时，显然只能线性扫描所有楼层：
def dp(K, N):
if K == 1: return N
if N == 0: return 0
...
添加一个备忘录消除重叠子问题：
def superEggDrop(K: int, N: int):
memo = dict()
def dp(K, N) -> int:
# base case
if K == 1: return N
if N == 0: return 0
# 避免重复计算
if (K, N) in memo:
return memo[(K, N)]
res = float('INF')
# 穷举所有可能的选择
for i in range(1, N + 1):
res = min(res,
max(
dp(K, N - i),
dp(K - 1, i - 1)
) + 1
)
# 记入备忘录
memo[(K, N)] = res
return res
return dp(K, N)
如果我们直接暴力转移求解每个状态的 dp 值，时间复杂度是为 
，即一共有 O(KN) 个状态，对于每个状态枚举扔鸡蛋的楼层 X，需要 O(N) 的时间。这无疑在当前数据范围下是会超出时间限制的，因此我们需要想办法优化枚举的时间复杂度。
我们观察到 dp(K,N) 是一个关于 N 的单调递增函数，也就是说在鸡蛋数 K 固定的情况下，楼层数 N 越多，需要的步数一定不会变少。在上述的状态转移方程中，第一项 
是一个随 X 的增加而单调递增的函数，第二项 
是一个随着 XX 的增加而单调递减的函数。
这如何帮助我们来优化这个问题呢？当 X 增加时，
单调递增而
单调递减，我们可以想象在一个直角坐标系中，横坐标为 X，纵坐标为和。当一个函数单调递增而另一个函数单调递减时，我们如何找到一个位置使得它们的最大值最小呢？
如上图所示，如果这两个函数都是连续函数，那么我们只需要找出这两个函数的交点，在交点处就能保证这两个函数的最大值最小。但在本题中，和都是离散函数，也就是说，X 的值只能取 1, 2, 3等等。在这种情况下，我们需要找到最大的满足 
的
，以及最小的满足 
的 
，对应到上图中，就是离这两个函数（想象中的）交点左右两侧最近的整数。
我们只需要比较在 和 处两个函数的最大值，取一个最小的作为 X 即可。在数学上，我们可以证明出 和 相差 1，这也是比较显然的，因为它们正好夹住了那个想象中的交点，并且相距尽可能地近。因此我们就可以使用二分查找的方法找出，再得到 ：
- 我们在所有满足条件的 XX 上进行二分查找。对于状态 (K,N) 而言，X 即为 [1, N] 中的任一整数；
- 在二分查找的过程中，假设当前这一步我们查找到了
，如果 
，那么真正的 一定在 
的左侧，否则真正的 在 的右侧。
二分查找的写法因人而异，本质上我们就是需要找到最大的满足 的 ，根据 进行二分边界的调整。在得到了 后，我们可以知道即为 
，此时我们只需要比较 
和 
，取较小的那个对应的位置作为 X 即可。
这样一来，对于给定的状态 (K,N)，我们只需要 O(logN) 的时间，通过二分查找就能得到最优的那个 X，因此时间复杂度从 降低至
，可以通过本题。
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
memo = {}
def dp(k, n):
if (k, n) not in memo:
if n == 0:
ans = 0
elif k == 1:
ans = n
else:
lo, hi = 1, n
# keep a gap of 2 X values to manually check later
while lo + 1 < hi:
x = (lo + hi) // 2
t1 = dp(k-1, x-1)
t2 = dp(k, n-x)
if t1 < t2:
lo = x
elif t1 > t2:
hi = x
else:
lo = hi = x
ans = 1 + min(max(dp(k-1, x-1), dp(k, n-x))
for x in (lo, hi))
memo[k, n] = ans
return memo[k, n]
return dp(K, N)
三、疑难解答
这个问题很复杂，但是算法代码却十分简洁，这就是动态规划的特性，穷举加备忘录/DP table 优化，真的没啥新意。
首先，有读者可能不理解代码中为什么用一个 for 循环遍历楼层[1..N]，也许会把这个逻辑和之前探讨的线性扫描混为一谈。其实不是的，这只是在做一次「选择」。
比方说你有 2 个鸡蛋，面对 10 层楼，你得拿一个鸡蛋去某一层楼扔对吧？那选择去哪一层楼扔呢？不知道，那就把这 10 层楼全试一遍。至于鸡蛋碎没碎，下次怎么选择不用你操心，有正确的状态转移，递归会算出每个选择的代价，我们取最优的那个就是最优解。
四、重写状态转移
前文 动态规划：不同的定义产生不同的解法 就提过，找动态规划的状态转移本就是见仁见智，比较玄学的事情。不同的状态定义可以衍生出不同的解法，其解法和复杂程度都可能有巨大差异。这里就是一个很好的例子。
再回顾一下我们之前定义的dp数组含义：
def dp(k, n) -> int
# 当前状态为 k 个鸡蛋，面对 n 层楼
# 返回这个状态下最少的扔鸡蛋次数
用 dp 数组表示的话也是一样的：
dp[k][n] = m
# 当前状态为 k 个鸡蛋，面对 n 层楼
# 这个状态下最少的扔鸡蛋次数为 m
按照这个定义，就是确定当前的鸡蛋个数和面对的楼层数，就知道最小扔鸡蛋次数。最终我们想要的答案就是dp(K, N)的结果。
这种思路下，肯定要穷举所有可能的扔法的，用二分搜索优化也只是做了「剪枝」，减小了搜索空间，但本质思路没有变，只不过是更聪明的穷举。
现在，我们稍微修改dp数组的定义，确定当前的鸡蛋个数和最多允许的扔鸡蛋次数，就知道能够确定F的最高楼层数。
有点绕口，具体来说是这个意思：
dp[k][m] = n
# 当前有 k 个鸡蛋，可以尝试扔 m 次鸡蛋
# 这个状态下，最坏情况下最多能确切测试一栋 n 层的楼
# 比如说 dp[1][7] = 7 表示：
# 现在有 1 个鸡蛋，允许你扔 7 次;
# 这个状态下最多给你 7 层楼，
# 使得你可以确定楼层 F 使得鸡蛋恰好摔不碎
# （一层一层线性探查嘛）
这其实就是我们原始思路的一个「反向」版本，我们先不管这种思路的状态转移怎么写，先来思考一下这种定义之下，最终想求的答案是什么？
我们最终要求的其实是扔鸡蛋次数m，但是这时候m在状态之中而不是dp数组的结果，可以这样处理：
int superEggDrop(int K, int N) {
int m = 0;
while (dp[K][m] < N) {
m++;
// 状态转移...
}
return m;
}
题目不是给你K鸡蛋，N层楼，让你求最坏情况下最少的测试次数m 吗？while循环结束的条件是dp[K][m] == N，也就是给你K个鸡蛋，允许测试m次，最坏情况下最多能测试N层楼。
注意看这两段描述，是完全一样的！所以说这样组织代码是正确的，关键就是状态转移方程怎么找呢？还得从我们原始的思路开始讲。之前的解法配了这样图帮助大家理解状态转移思路：
这个图描述的仅仅是某一个楼层i，原始解法还得线性或者二分扫描所有楼层，要求最大值、最小值。但是现在这种dp定义根本不需要这些了，基于下面两个事实：
1、无论你在哪层楼扔鸡蛋，鸡蛋只可能摔碎或者没摔碎，碎了的话就测楼下，没碎的话就测楼上。
2、无论你上楼还是下楼，总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）。
根据这个特点，可以写出下面的状态转移方程：dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1dp[k][m - 1]就是楼上的楼层数，因为鸡蛋个数k不变，也就是鸡蛋没碎，扔鸡蛋次数m减一；dp[k - 1][m - 1]就是楼下的楼层数，因为鸡蛋个数k减一，也就是鸡蛋碎了，同时扔鸡蛋次数m减一。
PS：这个m为什么要减一而不是加一？之前定义得很清楚，这个m是一个允许的次数上界，而不是扔了几次。
至此，整个思路就完成了，只要把状态转移方程填进框架即可：
int superEggDrop(int K, int N) {
// m 最多不会超过 N 次（线性扫描）
int[][] dp = new int[K + 1][N + 1];
// base case:
// dp[0][..] = 0
// dp[..][0] = 0
// Java 默认初始化数组都为 0
int m = 0;
while (dp[K][m] < N) {
m++;
for (int k = 1; k <= K; k++)
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
}
return m;
}
如果你还觉得这段代码有点难以理解，其实它就等同于这样写：
for (int m = 1; dp[K][m] < N; m++)
for (int k = 1; k <= K; k++)
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
python：
def superEggDrop(self, K: int, N: int) -> int:
if N == 1: return 1
dp = [[0] * (N + 1) for _ in range(K + 1)]
m = 0
while dp[K][m] < N:
m += 1
for k in range(1, K+1):
dp[k][m] = dp[k][m-1] + dp[k-1][m-1] + 1
return m
看到这种代码形式就熟悉多了吧，因为我们要求的不是dp数组里的值，而是某个符合条件的索引m，所以用while循环来找到这个m而已。
这个算法的时间复杂度是多少？很明显就是两个嵌套循环的复杂度 O(KN)。
另外注意到dp[m][k]转移只和左边和左上的两个状态有关，所以很容易优化成一维dp数组，这里就不写了。
降维：
def superEggDrop(self, K: int, N: int) -> int:
dp = [0] * (K + 1)
m = 0
while dp[K] < N:
m += 1
for k in range(K, 0, -1):
# print(m, k)
dp[k] = dp[k - 1] + dp[k] + 1
return m
五、进一步思考
再往下就要用一些数学方法了，不具体展开，就简单提一下思路吧。
在刚才的思路之上，注意函数dp(m, k)是随着m单增的，因为鸡蛋个数k不变时，允许的测试次数越多，可测试的楼层就越高。
这里又可以借助二分搜索算法快速逼近dp[K][m] == N这个终止条件，时间复杂度进一步下降为 O(KlogN)，我们可以设g(k,m)等于……
不过可以肯定的是，根据二分搜索代替线性扫描 m 的取值，代码的大致框架肯定是修改穷举 m 的 for 循环：
// 把线性搜索改成二分搜索
// for (int m = 1; dp[K][m] < N; m++)
int lo = 1, hi = N;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (... < N) {
lo = ...
} else {
hi = ...
}
for (int k = 1; k <= K; k++)
// 状态转移方程
}
简单总结一下吧，第一个二分优化是利用了dp函数的单调性，用二分查找技巧快速搜索答案；第二种优化是巧妙地修改了状态转移方程，简化了求解了流程，但相应的，解题逻辑比较难以想到；后续还可以用一些数学方法和二分搜索进一步优化第二种解法。
若有收获，就点个赞吧
0 人点赞
