题解 | #丢棋子问题/鸡蛋掉落问题#

本题与leetcode887鸡蛋掉落问题相同，附上解释比较清晰的一个题解 https://leetcode-cn.com/problems/super-egg-drop/solution/ji-dan-diao-luo-xiang-jie-by-shellbye/

反向思考k个棋子扔m次的方法中，最关键的问题是dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1是怎么来的。正如评论中解释的：每次都选择在dp[k - 1][m - 1] + 1层扔。有两种情况：

如果鸡蛋碎了，我们首先排除了该层以上的所有楼层（不管这个楼有多高），而对于剩下的 dp[k-1][m-1] 层楼，我们一定能用 k-1 个鸡蛋在 t-1 步内求解。因此这种情况下，我们总共可以求解无限高的楼层。可见，这是一种非常好的情况，但并不总是发生。

如果鸡蛋没碎，我们首先排除了该层以下的 dp[k-1][m-1] 层楼，此时我们还有 k 个蛋和 m-1 步，那么我们去该层以上的楼层继续测得 dp[k][m-1] 层楼。因此这种情况下，我们总共可以求解 dp[k-1][m-1] + dp[k][m-1] + 1 层楼。所以，dp[k][m]取值为这种比较差的情况，而不是两种情况的结合。

public:
    int superEggDrop(int k, int n) {
        vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
        for(int j = 1; j <= n; j++){
            for(int i = 1; i <= k; i++){
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1] + 1;
                if(dp[i][j] >= n){
                    return j;
                }
            }
        }
        return n;
    }
};

但是这种写法超出了内存限制，在leetcode上是可以通过的，牛客上需要改为一维数组，把j单独拿出来作为全局变量res。

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    int solve(int n, int k) {
        // write code here
        if(n < 1 )
            return 0;
        if(k == 1) return n;
        int max = log2(n) + 1;
        if(k >= max) return max;
        vector<int> dp(k + 1 , 0);
        int res = 0;
        while(dp[k] < n){
            res++;
            for(int i = k; i > 0; i--){
                dp[i] += dp[i -1] + 1;
            }
        }
        return res;
    }
};