05 August 2008
两只鸡蛋掉落
1
2
3
4
5
class Solution {
public int twoEggDrop(int n) {
return (int) Math.ceil((Math.sqrt(1 + 8 * n) - 1) / 2);
}
}
此题是887. 鸡蛋掉落的简化版
我们用dp[i][j]表示有(i+1)枚鸡蛋(i从0开始),需要检测j层楼时最少的移动步数 首先我们考虑只有一枚鸡蛋的情况,由于只要一枚鸡蛋,因此我们只能逐层尝试,即从1楼到N楼,那么极限情况最多需要N次 接下来我们考虑两枚鸡蛋去检测j层楼的情况，假设我们在第k(k>0)层楼丢鸡蛋：
如果鸡蛋碎了,那么就转化为一枚鸡蛋去检测K-1层楼的问题 如果鸡蛋没有碎,那么就转化为了两枚鸡蛋去检测j-k层楼的问题 由于我们需要确保能检测出结果,因此需要取上述两个子问题中的较大值 因此dp方程的转化为： dp[0][j] = j dp[1][j] = min(max(dp[0][k-1],dp[1][j-k])+1) 注意:这里加1是因为当前检测需要一次,1<=k<=j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int twoEggDrop(int floors) {
int eggs = 2;
int dp[][] = new int[eggs+1][floors+1];
int c =0;
for(int i=0; i <= floors; i++){
dp[1][i] = i;
}
for(int f = 1; f <=floors; f++){
dp[2][f] = Integer.MAX_VALUE;
for(int k = 1; k <=f ; k++){
c = 1 + Math.max(dp[1][k-1], dp[2][f-k]); //the egg breaks on current floor or the egg dosen't break on the current floor. Take the worst case
if(c < dp[2][f])
dp[2][f] = c;
}
}
return dp[eggs][floors];
}
}