BiliBili
YouTube
原题
中文
你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。
你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?
英文
You are given K
eggs, and you have access to a building with N
floors from 1
to N
.
Each egg is identical in function, and if an egg breaks, you cannot drop it again.
You know that there exists a floor F
with 0 <= F <= N
such that any egg dropped at a floor higher than F
will break, and any egg dropped at or below floor F
will not break.
Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X
(with 1 <= X <= N
).
Your goal is to know with certainty what the value of F
is.
What is the minimum number of moves that you need to know with certainty what F
is, regardless of the initial value of F
?
Example 1:
Input: K = 1, N = 2 Output: 2 Explanation: Drop the egg from floor 1. If it breaks, we know with certainty that F = 0. Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1. If it didn't break, then we know with certainty F = 2. Hence, we needed 2 moves in the worst case to know what F is with certainty.
Example 2:
Input: K = 2, N = 6 Output: 3
Example 3:
Input: K = 3, N = 14 Output: 4
Note:
1 <= K <= 100
1 <= N <= 10000
思路

代码
class Solution {
public:
int superEggDrop(int K, int N) {
vector<vector<int>> dp(K + 1, vector<int>(N + 1, INT_MAX));
for (int i = 0; i <= N; ++i) {
dp[0][i] = 0;
dp[1][i] = i;
}
for (int i = 0; i <= K; ++i) {
dp[i][0] = 0;
}
for (int k = 2; k <= K; ++k) {
for (int n = 1; n <= N; ++n) {
int l = 1, h = n, m = 0;
while (l <= h) {
m = l + (h - l) / 2;
int b = dp[k - 1][m - 1], nb = dp[k][n - m];
if (b > nb) {
h = m - 1;
} else {
l = m + 1;
}
dp[k][n] = min(dp[k][n], max(b, nb) + 1);
}
}
}
return dp[K][N];
}
};
复杂度分析
- 时间复杂度:O(N*K*\log N)
- 空间复杂度:O(N*K)
参考
原题:https://leetcode.com/problems/super-egg-drop/
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/leetcode-887-super-egg-drop/
2exactitude
[…] 阅读原文 […]