lc887. 鸡蛋掉落

题目连接:887. 鸡蛋掉落 - 力扣(LeetCode)

题解

假设 dp[i][j] 代表 i 个鸡蛋移动 j 次最多能覆盖多少层楼,可以得到递推公式 dp[i][j]=dp[i-1][j-1] + dp[i][j-1] + 1,题目转换成求 dp[k][j]>=n 时最小的 j。这个递推公式增长速度很快,超过 n 后强制修改成 n 即刻。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int dp[101][10001];
int superEggDrop(int k, int n) {
memset(dp, 0, sizeof dp);
for(int i=1;i<=k;i++) {
for(int j=1;j<=n;j++) {
if(i==1) {
dp[i][j]=j;
} else {
if (dp[i-1][j-1]>=n || dp[i][j-1]>=n) {
dp[i][j] = n + 1;
}
else
dp[i][j] = 1 + dp[i-1][j-1] + dp[i][j-1];
}
if(i==k&&dp[i][j]>=n) {
return j;
}
}
}
return n;
}
};

DFS 超时代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int ans[101][10000+1];
int dfs(int k, int n) {
if (ans[k][n]!= -1) {
return ans[k][n];
}
if (k == 1) return n;
if (n == 1) return 1;
int mi = n;
for (int i = 1; i< n; i ++) {
int f1 = dfs(k-1, i-1);
int f2 = dfs(k, n-i);
mi = min(1+max(f1, f2), mi);
}
ans[k][n] = mi;
return mi;
}
int superEggDrop(int k, int n) {
memset(ans, 0xff ,sizeof ans);
return dfs(k,n);
}
};

作者

Ryen Xiang

发布于

2024-03-23

更新于

2024-08-05

许可协议


网络回响

评论