class Solution {
public:
int superEggDrop(int k, int n) {
}
};
887. 鸡蛋掉落
给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
示例 1：
输入：k = 1, n = 2 输出：2 解释： 鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 如果它没碎，那么肯定能得出 f = 2 。 因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。
示例 2：
输入：k = 2, n = 6 输出：3
示例 3：
输入：k = 3, n = 14 输出：4
提示：
1 <= k <= 1001 <= n <= 104原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2024-10-14 09:50:00
func superEggDrop1(k, n int) int {
f := make([][]int, n+1)
f[0] = make([]int, k+1)
for i := 1; ; i++ {
f[i] = make([]int, k+1)
for j := 1; j <= k; j++ {
f[i][j] = f[i-1][j] + f[i-1][j-1] + 1
}
if f[i][k] >= n {
return i
}
}
}
// 空间优化
func superEggDrop(k, n int) int {
f := make([]int, k+1)
for i := 1; ; i++ {
for j := k; j > 0; j-- {
f[j] += f[j-1] + 1
}
if f[k] >= n {
return i
}
}
}
cpp 解法, 执行用时: 3 ms, 内存消耗: 7.5 MB, 提交时间: 2024-10-14 09:49:20
class Solution {
public:
int superEggDrop1(int k, int n) {
vector<vector<int>> f(n + 1, vector<int>(k + 1));
for (int i = 1; ; i++) {
for (int j = 1; j <= k; j++) {
f[i][j] = f[i - 1][j] + f[i - 1][j - 1] + 1;
}
if (f[i][k] >= n) {
return i;
}
}
}
// 空间优化
int superEggDrop(int k, int n) {
vector<int> f(k + 1);
for (int i = 1; ; i++) {
for (int j = k; j > 0; j--) {
f[j] += f[j - 1] + 1;
}
if (f[k] >= n) {
return i;
}
}
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 39.3 MB, 提交时间: 2024-10-14 09:48:41
class Solution {
public int superEggDrop1(int k, int n) {
// f[i][j]: 有 i 次操作机会和 j 枚鸡蛋的情况下，可以让我们能确定 f 值的最大建筑层数。
int[][] f = new int[n + 1][k + 1];
for (int i = 1; ; i++) {
for (int j = 1; j <= k; j++) {
f[i][j] = f[i - 1][j] + f[i - 1][j - 1] + 1;
}
if (f[i][k] >= n) {
return i;
}
}
}
// 空间优化
public int superEggDrop(int k, int n) {
int[] f = new int[k + 1];
for (int i = 1; ; i++) {
for (int j = k; j > 0; j--) {
f[j] += f[j - 1] + 1;
}
if (f[k] >= n) {
return i;
}
}
}
}
python3 解法, 执行用时: 776 ms, 内存消耗: 24.6 MB, 提交时间: 2022-08-22 15:58:40
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)
python3 解法, 执行用时: 2740 ms, 内存消耗: 15.2 MB, 提交时间: 2022-08-22 15:58:03
class Solution:
def superEggDrop(self, k: int, n: int) -> int:
# Right now, dp[i] represents dp(1, i)
dp = list(range(n + 1))
dp2 = [0] * (n + 1)
for k in range(2, k + 1):
# Now, we will develop dp2[i] = dp(j, i)
x = 1
for m in range(1, n + 1):
# Let's find dp2[m] = dp(j, m)
# Increase our optimal x while we can make our answer better.
# Notice max(dp[x-1], dp2[m-x]) > max(dp[x], dp2[m-x-1])
# is simply max(T1(x-1), T2(x-1)) > max(T1(x), T2(x)).
while x < m and max(dp[x - 1], dp2[m - x]) >= max(dp[x], dp2[m - x - 1]):
x += 1
# The final answer happens at this x.
dp2[m] = 1 + max(dp[x - 1], dp2[m - x])
dp = dp2[:]
return dp[-1]
python3 解法, 执行用时: 100 ms, 内存消耗: 22.9 MB, 提交时间: 2022-08-22 15:57:24
class Solution:
def superEggDrop(self, k: int, n: int) -> int:
if n == 1:
return 1
f = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, k + 1):
f[1][i] = 1
ans = -1
for i in range(2, n + 1):
for j in range(1, k + 1):
f[i][j] = 1 + f[i - 1][j - 1] + f[i - 1][j]
if f[i][k] >= n:
ans = i
break
return ans