LeetCode 887. 鸡蛋掉落题解

LeetCode 887. 鸡蛋掉落

附上大佬的题解

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中重复使用这枚鸡蛋。

请你计算并返回要确定 f 确切的值的最小操作次数是多少？

示例 1：

输入：k = 1, n = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。
如果它没碎，那么肯定能得出 f = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。

示例 2：

输入：k = 2, n = 6
输出：3

示例 3：

输入：k = 3, n = 14
输出：4

提示：

1 <= k <= 100
1 <= n <= 104

思路一：二分

题目中给了我们 K 个鸡蛋，以及 N 层的一栋大楼。对于鸡蛋来说，有一个临界点 f ,在楼层 f 之上扔鸡蛋的话，鸡蛋会碎。在 f 层之下扔鸡蛋则不会碎。需要我们求出找到这个零界点所需的最小操作数。
刚看到题时的第一个思路就是二分，时间复杂度 O(logN),看起来很美好，可是在题目中限制了鸡蛋的个数。如果鸡蛋的个数比二分需要的鸡蛋数要多，使用二分自然没问题。可是如果鸡蛋的数目比二分小的话就不能直接使用二分来做，需要我们每次操作尽可能最优。
这是就有了另外一个思路，枚举所有的情况，选择最优的！

思路二：枚举

鸡蛋在每一层楼扔下去都有碎 or 完好两种情况，即我们需要枚举每次人鸡蛋的情况，对于每次鸡蛋碎 or 完好的情况下再次枚举其他情况，直到枚举完所有情况。
直接暴力枚举的话，很明显复杂度是阶乘级别的，所以必然是需要优化一下的 --> 剪枝
既然直接搜索枚举用不了，而且枚举的时候可以分成若干个小情况，每种小情况的最优解是唯一的，然后通过小的最优解求出最终的最优解。所以可以考虑动态规划

思路三：动态规划

对于题目中的描述，有 k,n 两个变量与之有关，可以使用二维的 dp

dp[i][j] /表示已经扔了 i 个鸡蛋，当前在前 j 层扔鸡蛋的最小扔鸡蛋次数 --> dp 数组可初始化为一个极大值

所以需要枚举 1 ～ j 层楼的情况，找出最优解，状态转移方程如下

//假设当前在第 x 层楼扔鸡蛋， 1 <= x <= j	
dp[i][j] = Min(dp[i][j], Max(dp[i - 1][x - 1], dp[i][j - x]) + 1);
dp[i - 1][x - 1]//x 楼扔鸡蛋，鸡蛋碎了，所以需要前 i - 1 个鸡蛋在前 x - 1 层楼的最小操作数
dp[i][j - x]//	x 楼扔鸡蛋，鸡蛋完好，需要前 i 个鸡蛋在x 楼之后的 j - x 层楼的最小操作数

dp 数组初始化

dp[i][0] = 0;//第 0 层楼不需要扔，结果为 0
dp[1][j] = j;//只有一个鸡蛋的情况下，只能找到最优的情况扔，需要每层楼都扔一次

JS 代码

var superEggDrop = function(k, n) {
    let dp = new Array(k + 1).fill(Infinity).map(() => new Array(n + 1).fill(Infinity));
    for (let i = 1; i <= n; i++) dp[1][i] = i;
    for (let i = 0; i <= k; i++) dp[i][0] = 0;
    for (let i = 2; i <= k; i++) {//鸡蛋数
        for (let j = 1; j <= n; j++) {//楼层总数
            for (let l = 1; l <= j; l++) {//枚举扔鸡蛋的楼层
                dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][l - 1], dp[i][j - l]) + 1);//鸡蛋 碎 没碎                
            }
        }
    }
    return dp[k][n];
};

使用二分优化动态规划的时间复杂度

此解法的时间复杂度为 (kn^2),而且对于dp[i - 1][x - 1]来说随着 x 的增加，其值为不递减的状态（对应：鸡蛋碎 or 不碎两种情况）。对于dp[i][j - x]来说，随着 x 的增加，其值为不递增的状态。因为，我们需要找到的是最小化的最大值，也就是说需要找到dp[i - 1][x - 1] 和 dp[i][j - x]相等时的临界情况，或者距离相等最近的临界情况

由于dp[i][j]不递减，也就是说这个数组是有序的，所以可以使用二分搜索来找到这个临界情况，这样的话，算法的时间复杂度就变为了 (knlogn),具体 JS 代码如下

var superEggDrop = function(k, n) {
    let dp = new Array(k + 1).fill(Infinity).map(() => new Array(n + 1).fill(Infinity));
    for (let i = 1; i <= n; i++) dp[1][i] = i;
    for (let i = 0; i <= k; i++) dp[i][0] = 0;
    for (let i = 2; i <= k; i++) {//鸡蛋树
        for (let j = 1; j <= n; j++) {//楼层总数
            // for (let l = 1; l <= j; l++) {//枚举扔鸡蛋的楼层 
            //     dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][l - 1], dp[i][j - l]) + 1);//鸡蛋 碎 没碎 --> 找一个最大的较小值 --> 两者单调性一个递增，一个递减，找他们相等时的边界条件 --> 二分               
            // }
            let [l, r] = [1, j];//扔鸡蛋的楼层
            while (l < r) {
                const mid = (l + r) >> 1;
                if (dp[i - 1][mid - 1] >= dp[i][j - mid]) r = mid;
                else l = mid + 1;
            }
            dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][l - 1], dp[i][j - l]) + 1);
        }
    }
    return dp[k][n];
};

由于 dp[i] 只与 dp[i - 1] 有关，所以可以使用滚动数组优化的方式将空间复杂度由 (n^2) 降为 (n), 使用 2 * (n + 1) 的数组，0 为 i - 1，1 为即可。在每次最内层循环结束时，将 1 移动到 0，再初始化 1。
除此之外，还有数学上的解法，可以参考博客开始部分的附上大佬的题解