LeetCode 887 Super Egg Drop
思考
首先要注意,让求的是需要的最少的步数,而不是目标楼层号。
使用动态规划求解时,要想明白状态要如何定义,这里可以为剩余的鸡蛋数目和要测试的楼层数目。
另一个困惑点,当我们在做选择的时候,我们怎么知道鸡蛋碎还是没碎?我们怎么判别?实际上我们没有办法判别碎还是没碎,由于题目要求是 Your goal is to know with certainty what the value of F is.
,因此我们选择最坏的情况就好。
第一次尝试
class Solution {
int[][] data;
public int superEggDrop(int K, int N) {
data = new int[K+1][N+1];
return dp(K, N);
}
private int dp(int k, int n) {
if(data[k][n] != 0) return data[k][n];
if(n == 0) return 0;
if(k == 1) return n;
data[k][n] = Integer.MAX_VALUE;
for(int i=1;i<=n;i++) {
int worstCase = Math.max(dp(k-1, i)+1, dp(k, n-i)+1);
data[k][n] = Math.min(data[k][n], worstCase);
}
return data[k][n];
}
}
WA,原因在于鸡蛋碎的情况状态转移写错了,应为 dp(k-1,i-1)。
第二次尝试
class Solution {
int[][] data;
public int superEggDrop(int K, int N) {
data = new int[K+1][N+1];
return dp(K, N);
}
private int dp(int k, int n) {
if(data[k][n] != 0) return data[k][n];
if(n == 0) return 0;
if(k == 1) return n;
data[k][n] = Integer.MAX_VALUE;
for(int i=1;i<=n;i++) {
int worstCase = Math.max(dp(k-1, i-1)+1, dp(k, n-i)+1);
data[k][n] = Math.min(data[k][n], worstCase);
}
return data[k][n];
}
}
超时了。。。检查了一下,备忘录写的没问题,这意味着我们需要换思路。 (其实还可以用二分搜索进行优化的,这个之后再写吧。)
第三次尝试
dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
此处 dp[m][k]
意味着 m 次移动以及 k 个鸡蛋,我们能确定的楼层数目。最令人不解的地方便在于为什么是加起来,而非取一个最值。
New DP definition: If you give me k egg, let me drop m times, I can try out maximum dp[m][k] floors. Based on this definition, the result is some m, which cases dp[m][K] equals N. The transfer equation is based on the following facts:
- No matter which floor you try, the egg will only break or not break, if break, go downstairs, if not break, go upstairs.
- No matter you go up or go down, the num of all the floors is always upstairs + downstairs + the floor you try, which is dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1.
这里就说的很清楚,这个等式是由 num of all the floors = upstairs + downstairs + the floor you try
转换来的。
class Solution {
public int superEggDrop(int K, int N) {
int[][] dp = new int[K+1][N+1];
int m=0;
while(dp[K][m]<N) {
m++;
for(int k=1;k<=K;k++) {
dp[k][m] = dp[k][m-1]+dp[k-1][m-1]+1;
}
}
return m;
}
}
这个是真的不好想啊。。。
错误记录
语法错误
- 忘记加分号
- Math.max()
Links: leetcode-887-super-egg-drop