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:

1. No matter which floor you try, the egg will only break or not break, if break, go downstairs, if not break, go upstairs.
2. 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;
    }
}

这个是真的不好想啊。。。

错误记录

语法错误

1. 忘记加分号
2. Math.max()

Links: leetcode-887-super-egg-drop