LeetCode 887 Super Egg Drop
动态规划问题 LeetCode 2020-03-10 22:37:23 2022-02-19 21:21:48 1044 次浏览概述
思考
首先要注意，让求的是需要的最少的步数，而不是目标楼层号。
使用动态规划求解时，要想明白状态要如何定义，这里可以为剩余的鸡蛋数目和要测试的楼层数目。
另一个困惑点，当我们在做选择的时候，我们怎么知道鸡蛋碎还是没碎？我们怎么判别？实际上我们没有办法判别碎还是没碎，由于题目要求是 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()
2022年2月19日的尝试
class Solution {
public:
vector<vector<int>> dp;
int superEggDrop(int k, int n) {
dp.resize(k+1, vector<int>(n+1, -1));
return helper(k, n);
}
int helper(int k, int n) {
if (n == 0) return 0;
if (k == 0) return INT_MAX;
if (dp[k][n] != -1) return dp[k][n];
dp[k][n] = INT_MAX;
for (int i = 1; i <= n; i ++) {
dp[k][n] = min(dp[k][n], max(helper(k-1, i-1), helper(k, n-i)));
}
dp[k][n] += 1;
return dp[k][n];
}
};
超时了，为啥 base case 写 if (k == 0) return INT_MAX; 也 okay 呢？
k 为 1 时，由于 helper(k-1, i-1) = INT_MAX，导致 dp[k][n] 为 INT_MAX，为啥这个 work 呢？
额，想错了，n == 0 时不就不是 INT_MAX 了么。。。
上面的时间复杂度：O(KN^2)，因为函数本身 O(N)，每个子问题调用一次函数，一共 KN 个子问题。
二分搜索优化
https://mp.weixin.qq.com/s/7XPGKe7bMkwovH95cnhang
class Solution {
public:
vector<vector<int>> dp;
int superEggDrop(int k, int n) {
dp.resize(k+1, vector<int>(n+1, -1));
return helper(k, n);
}
int helper(int k, int n) {
if (n == 0) return 0;
if (k == 0) return INT_MAX;
if (dp[k][n] != -1) return dp[k][n];
dp[k][n] = INT_MAX;
int l = 1, r = n;
while (l <= r) {
int m = (l + r) / 2;
int broken = helper(k-1,m-1);
int notBroken = helper(k, n-m);
if (broken > notBroken) { // we are too high!
r = m - 1;
dp[k][n] = min(dp[k][n], broken);
} else { // we are too low!
l = m + 1;
dp[k][n] = min(dp[k][n], notBroken);
}
}
dp[k][n] += 1;
return dp[k][n];
}
};
可以这样理解，当本次实验，broken 用的次数比 notBroken 要多时，说明我们太高， 此时如果我们选更高的高度话，broken 的值肯定要更大，这样总体的值就更大了（因为我们是取 max）， 所以最优解肯定不在上面那个范围。
Links: leetcode-887-super-egg-drop