887. 鸡蛋掉落

[Geekhyt]

原题链接

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。
如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

两种思路定义状态转移方程

三个变量：k、n、f，固定其中 2 个即可求出另外一个。

思路一

固定鸡蛋个数和楼层数，求出最少扔鸡蛋次数。

dp[k][n] = f // 当前有 k 个鸡蛋， n 层楼，最少扔鸡蛋次数为 f

思路一就是穷举出所有可能的扔鸡蛋的方法，可以在穷举的基础上使用记忆化和二分搜索进行优化。

思路二

逆向思维，固定鸡蛋个数和扔鸡蛋次数，求出楼层数。

dp[k][f] = n // 当前有 k 个鸡蛋，可以尝试扔 f 次，最坏情况下最多能确定 n 层楼

思考以下两点：

1. 从楼上扔下鸡蛋只有两种可能，要么鸡蛋碎了要么没碎，如果鸡蛋碎了就继续在楼下扔，如果鸡蛋没有碎就在楼上扔
2. 总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）

我们使用思路二进行求解。

状态定义

dp[i][j]： 有 i 个鸡蛋，扔 j 次鸡蛋可测得的最多楼层

状态转移方程

dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1

理解

• dp[i][j - 1]：楼上的楼层数，鸡蛋没碎 i 不变，扔鸡蛋次数 j 减 1
• dp[i - 1][j - 1]： 楼下的楼层数，鸡蛋碎了 i - 1，同时扔鸡蛋次数 j 减 1

降维

观察状态转移方程，状态转移方程中 [j - 1] 可以省略，所以得出：

dp[i] = dp[i] + dp[i - 1] + 1

dp[i]：表示当前次数下使用 i 个鸡蛋可以测出的最高楼层

while 循环的结束条件是 dp[K][j] < N， 表示 K 个鸡蛋，测试 j 次，最坏情况下最多可以测试 N 层楼。

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

• 时间复杂度: O(Kj)
• 空间复杂度: O(KN)