LeetCode 887 Super Egg Drop

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2020-03-10 22:37:23
    编辑于：2022-02-19 21:21:48
    浏览量：1698

概述

题目链接

思考

首先要注意，让求的是需要的最少的步数，而不是目标楼层号。

使用动态规划求解时，要想明白状态要如何定义，这里可以为剩余的鸡蛋数目和要测试的楼层数目。

另一个困惑点，当我们在做选择的时候，我们怎么知道鸡蛋碎还是没碎？我们怎么判别？实际上我们没有办法判别碎还是没碎，由于题目要求是 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.

Source

这里就说的很清楚，这个等式是由 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