BiliBili

YouTube

## 原题

### 英文

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. 1 <= K <= 100
2. 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)$

## 参考

欢迎分享，引用。若转载，请联系我，谢谢配合。

0 0 votes
Article Rating
Subscribe

1 评论
Inline Feedbacks
View all comments

[…] 阅读原文 […]