算法-鸡蛋掉落问题.md

题目

本题来自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

提示：

1. 1 <= K <= 100
2. 1 <= N <= 10000

动态规划解法

这道题困扰了我很久，由于我是先按照各类算法类型进行学习，所以先从题解的动态规划考虑。leetcode的题解里，从正向思维使用动态规划解法，题解提示会超时。。。所以需要逆向思维，题目需要求得最小的移动次数，可以转换为移动最少次数最多能确定多少层的F。

若有dp=[]，我们用dp[i][j]来表示用i个鸡蛋移动j步能确定楼层。

• 当i=0时，dp[0][j]=0。
• 当i=1时，dp[1][j]=j。
• 当j=0时，dp[i][0]=0。
• 当j=1时，dp[i][1]=1。

有了初始值后，接着考虑动态转移方程。我们不枚举楼的高度，我们枚举操作的次数，并想知道在t次操作，K个鸡蛋的情况下，能确定F的最大楼层高度是多少，假设它为 f(t,K) ，很明显 f(t,K) 随t的增加而增大，因为操作次数越多，能确定的楼层数肯定越多，所以我们需要找到最小的一个 t 使得 f(t,K)>=N 。

假设f(t,k)>=n，那么在n层楼里的X层扔下鸡蛋。

• 假如鸡蛋碎了，说明楼层太高了，那我们就要满足，在x-1层楼里，用k-1个鸡蛋移动t-1次来确定剩余楼层的F，所以有不等式 f(t-1,k-1)>=x-1。
• 假如鸡蛋没碎，那么我们就要满足，在n-x层楼里，用k个鸡蛋移动t-1次来确定剩余的楼层的F，所以有不等式f(t-1,k)>=n-x。

将两个条件相加，消去x得到：f(t-1,k-1)+f(t-1,k)>=n-1，也就是f(t-1,k-1)+f(t-1,k)+1>=n。而我们有f(t,k)>=n。所以f(t,k)=f(t-1,k-1)+f(t-1,k)+1。

以上的动态规划方程，网上也有从不同逻辑推演得到，但多是从结果出发找逻辑，令人难以理解，也是困扰我的地方。而这里，是我找到的最易于理解的逻辑，从扔鸡蛋后产生的两个不等式，推算出最终的方程。

代码如下：

/**
 * @param {number} K
 * @param {number} N
 * @return {number}
 */
var superEggDrop = function(K, N) {
  let dp = []
  for (let i = 0; i <= K; i++) {
    dp[i] = []
    dp[i][0] = 0
  }
  for (let j = 1; j <= N; j++) {
    dp[0][j] = 0
    dp[1][j] = j
    for (let i = 1; i <= K; i++) {
      dp[i][0] = 0
      dp[i][1] = 1
      dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1] + 1
      if (dp[i][j] >= N) return j
    }
  }
}