题目描述
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。你知道存在楼层 F ，满足 0 <= F <= N ，任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。你的目标是确切地知道 F 的值是多少。无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？（即最少扔几次）
输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
解题思路
这个题挺难的，面试还爱问。最直接的思路是线性扫描，但是这样效率不高。实际上，如果本题不限制鸡蛋个数的话，二分思路显然可以得到最少尝试的次数，但问题是，现在给你限制了鸡蛋的个数
K
，直接使用二分思路就不行了（比如说只给你
1
个鸡蛋，
7
层楼，你敢用二分吗？）。我的实现。
- 动态规划：前文「不同定义有不同解法」就提过，找动态规划的状态转移本就是见仁见智，比较玄学的事情，不同的状态定义可以衍生出不同的解法，其解法和复杂程度都可能有巨大差异。这里就是一个很好的例子。
- 如果根据“问什么定义什么”的思路，本题的状态表示应该为：
这种定义方式效率比较低，会报超时错误。具体解法和代码请参照大佬题解和我的实现。# 用带有两个状态参数的 dp 函数来表示状态转移 def dp(k, n) -> int # 当前状态为 k 个鸡蛋，面对 n 层楼 # 返回这个状态下最少的扔鸡蛋次数 # 或用二维的 dp 数组表示的话也是一样的 dp[k][n] = m # 当前状态为 k 个鸡蛋，面对 n 层楼 # 这个状态下最少的扔鸡蛋次数为 m -
重新定义状态转移：（状态表示比较难理解，推荐记一下，这算是个很难的动态规划题了）
现在，我们稍微修改下
dp
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
层楼。
下面最重要的是要明确状态转移方程，有下面两个事实：
- 无论你在哪层楼扔鸡蛋（所以不需要穷举楼层了），鸡蛋只可能摔碎或者没摔碎（两种可能），碎了的话就测楼下，没碎的话就测楼上。
- 无论你上楼还是下楼，总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）。
dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1
dp[k][m - 1]
k
m
dp[k - 1][m - 1]
k-1
m
[LeetCode] 887、鸡蛋掉落
- 如果根据“问什么定义什么”的思路，本题的状态表示应该为：
参考代码
解法一（会超时）
class Solution:
def superEggDrop(self, K: int, N: int) -> 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)
解法二（可AC）
class Solution {
public:
int superEggDrop(int K, int N) {
// 定义dp[K+1][N+1]，m 最多不会超过 N 次（线性扫描）
vector<vector<int> > dp(K + 1, vector<int>(N + 1, 0));
// base case:
// dp[0][..] = 0
// dp[..][0] = 0
int m = 0;
while(dp[K][m] < N){
m++;
for(int k = 1; k <= K; k++)
dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1; // 碎 + 没碎 + 1
}
return m;
}
};
优化成一维dp
/**
* 鸡蛋掉落，鹰蛋（Leetcode 887）：（经典dp）
* 有 K 个鸡蛋，有 N 层楼，用最少的操作次数 F 检查出鸡蛋的质量。
*
* 思路：
* 本题应该逆向思维，若你有 K 个鸡蛋，你最多操作 F 次，求 N 最大值。
*
* dp[k][f] = dp[k][f-1] + dp[k-1][f-1] + 1;
* 解释：
* 0.dp[k][f]：如果你还剩 k 个蛋，且只能操作 f 次了，所能确定的楼层。
* 1.dp[k][f-1]：蛋没碎，因此该部分决定了所操作楼层的上面所能容纳的楼层最大值
* 2.dp[k-1][f-1]：蛋碎了，因此该部分决定了所操作楼层的下面所能容纳的楼层最大值
* 又因为第 f 次操作结果只和第 f-1 次操作结果相关，因此可以只用一维数组。
*
* 时复：O(K*根号(N))
*/
public int superEggDrop(int K, int N) {
int[] dp = new int[K + 1];
int ans = 0; // 操作的次数
while (dp[K] < N){
for (int i = K; i > 0; i--) // 从后往前计算
dp[i] = dp[i] + dp[i-1] + 1;
ans++;
}
return ans;
}
其中：
dp[2][3]
表示：