leetcode-鸡蛋掉落

鸡蛋掉落(难度：困难)

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再使用它，否则可以继续丢，鸡蛋的性能不会随着丢的次数增加而有所损耗。

假设存在一个中间楼层F，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 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

动态规划

这个方法可以观看李永乐的视频，比较好理解

复工复产找工作？先来看看这道面试题：双蛋问题

维护一个状态数组dp,dp[i][j]代表一共有 i 层楼的情况下，使用 j 个鸡蛋的最少实验的次数。

说明：

i 表示的是楼层的大小相对，不是绝对高度（第几层）的意思，例如楼层区间 [8, 9, 10] 的大小为 3。
j 表示可以使用的鸡蛋的个数，它是约束条件。

对于这个数组，我们可以对它的一些特殊情况进行初始化

只有一个鸡蛋：最少移动数就是楼层数。只有一层楼：永远只需要移动一次

那么接下来对于每一个高度i我们就需要进行枚举，在0到i之间选一个楼层k开始试验，k从1开始直到i，就可以依次填写这个数组

对于当前的楼层k，k >= 1 且 k <= i：

如果鸡蛋破碎，实验就得在 k 层以下做（不包括 k 层），这里已经使用了一个鸡蛋，简单来说就是楼层数减一，鸡蛋数减一，即求：dp[k - 1][j - 1]；

如果鸡蛋完好，那么就要去k楼层以上进行试验。那么对于表中的i层楼，剩下的楼层数就是i- k，所以这个时候即求：dp[i - k][j])

那么对于同一个k取值时存在摔碎与没摔碎两种情况，我们要去求最差情况，也就是两者之间的最大值

对于不同k之间的取值，我们需要取两者之间的最小值

代码如下：

var superEggDrop = function(K, N) {
    let dp = new Array(N + 1)
    for(let i = 0; i <= N; i++){
        dp[i] = new Array(K + 1).fill(i)
    }

    for(let i = 2; i <= N; i++){
        for(let j = 2; j <= K; j++){
            for (let k = 1; k <= i; k++) {
                dp[i][j] = Math.min(dp[i][j], Math.max(dp[k - 1][j - 1], dp[i - k][j]) + 1);
            }
        }
    }
    return dp[N][K]
};

在上述解法中，由于开辟了一个二维数组dp，所以空间复杂度为O(NK)。填表本身的时间复杂度为O(NK)， 但是对于表中的每一项（也就是每一个高度）,都要对从哪里开始实验进行枚举，所以时间复杂度变为O(KN^2)

所以不出意外，这道题提交直接TLE

动态规划（重写状态转移方程）

这道题可以进行一下逆行思维，将状态转移方程dp[i][j]看成，当你有j和鸡蛋，最多可以走i步，你最多可以验证dp[i][j]高的楼层

那么对于dp[i][j]来说，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1

j 个蛋，且只能操作 i 次了，所能确定的楼层。

```dp[i - 1][j]```：蛋没碎，因此该部分决定了所操作楼层的上面所能容纳的楼层最大值
```dp[i-1][j-1]```：蛋碎了，因此该部分决定了所操作楼层的下面所能容纳的楼层最大值

那么最终dp数组中最后一列中刚刚大于楼层数N的那一个数所在的行数就是最小操作数

![](https://img-blog.csdnimg.cn/20200411115431149.png)
代码如下：

```javascript
var superEggDrop = function(K, N) {
    let dp = new Array(N)
    for(let i = 0; i < N; i++){
        if(i === 0){
            dp[i] = new Array(K).fill(1)
        }
        else{
            dp[i] = new Array(K).fill(i + 1)
        }
    }

    for(let i = 1; i < N; i++){
        for(let j = 1; j < K; j++){
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + 1
        }
        if(dp[i][K - 1] >= N){
            return i + 1
        }
    }
    return dp[0][K - 1]
};

再优化

对于上述的dp数组我们发现，第 f 次操作结果只和第 f-1 次操作结果相关，因此我们可以把dp压缩成为一个一维数组，我们发现纵向最多允许操作数是顺序增长的，所以我们可以把纵向最大操作数取消，使用一个变量count递增来代替，保留鸡蛋数，dp[i]代表有i个鸡蛋时，当前count次操作后可以确认的楼层数。.

代码如下：

var superEggDrop = function(K, N) {
    let dp = new Array(K + 1).fill(0)
    let count = 0
    while(dp[K] < N){
        for(let i = K; i > 0; i--){
            dp[i] = dp[i] + dp[i - 1] + 1
        }
        count ++
    }
    return count
};