leetcode 887. 鸡蛋掉落

[xxleyi]

题：

你将获得 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 <= K <= 100
1 <= N <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/super-egg-drop
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解：

此题据说是谷歌的经典面试题。确实够劲。

此题的关键是搞懂怎么做。大部分题目在初看之后，总能有个暴力穷举的解决方案，虽然很可能行不通。但总归是个安慰嘛。

此题最容易挫败人的地方在于：读过题目之后，一脸懵逼，连暴力穷举的解决方案都想不出来。

遇到这种情况怎么办呢？只能耐心多理一理了。

理顺之后，就能想明白该怎么解决：

• K 个蛋，N 层楼，最佳策略肯定是把每一个蛋都用上，用上的意思是都摔碎
• 每一个蛋都摔碎，但要碎的有价值
• 假设只有一个蛋，想要找到 F 唯一奏效的策略就是从 1 层逐级往上，直到摔碎。最后就是楼层数 N
• 如果有两个蛋，那我们就可以利用起来，不用逐级往上，可以间隔开来，比如从 x 层扔
  • 如果蛋碎了，则 F 介于 [0, x), 即 (1, x - 1)
  • 如果蛋没碎，则 F 介于 [x + 1, N], 问题规模缩小，即 (2, N - x)
  • 则 (2, N) 有可能等于 1 + max{(1, x - 1), (2, N - x)}
  • 考虑到 x 的取值可能有哪些？对，有可能是 [1, N ] 中的任何一个
  • 则递推方程出来了 f(k, n) = 1 + min{ max{f(k - 1, x - 1), f(k, n - x)} }, x 介于 [1, n]

然后根据递归方程，就能使用带记忆的递归暴力求解了。

然后发现超时，之后观察递推方程自身的性质来逐步优化：

• 第一步，寻找 x 可以不用暴力遍历，可以使用二分查找，将复杂度降到 O(logn)
• 第二步，寻找 x 还可以不用每次都二分查找，因为外层循环 k 不变时，x 随内层循环 n 的减少而减少
• 也就是说，每一个内层循环下，x 随 n 的增大而增大，且自身具有单调性
• 也就是说，寻找 x 的复杂度，可以均摊成 O(1)

该是见代码的时候了：

// 自顶向下的解法，略粗暴，但有效
// 「循环不变式」隐藏的特别深，不够明显
var superEggDrop = function(K, N) {
  // 「循环不变式」相关的变量
  let cache = Array(K + 1)
  for (let i = 0; i <= K; i++) cache[i] = Array(N + 1)

  // 辅助函数：二分法查找最小值
  function bin(k, n) {
    // 二分法中必用的「循环不变式」相关的变量
    let lo = 1, hi = n
    while (true) {
      let mid = lo + (hi - lo) / 2 | 0
      let up = loop(k - 1, mid - 1)
      let down = loop(k, n - mid)
      // 判断循环是否终止
      if(up === down || lo + 1 >= hi) return Math.max(up, down)
      // 更新变量以确保「循环不变式」
      if (up < down) lo = mid
      else hi = mid
    }
  }

  // 暴力递归版循环函数
  function loop(k = K, n = N) {
    // 检查是否已经计算过
    if (cache[k][n]) return cache[k][n]
    // 正确更新 cache 以维护「循环不变式」
    if (k === 1) cache[k][n] = n
    else if (n === 0) cache[k][n] = 0
    else {
      // 自顶向下的递推方程
      cache[k][n] = 1 + bin(k, n)
    }
    // 循环终止时，返回正确答案
    return cache[k][n]
  }

  return loop()
};


// 改写为自底向上的迭代版循环函数
// 「循环不变式」以及相关变量变得清晰明确
// 注：测试用例规模过大时会报递归过深的错误，但其实已经是尾递归，只不过 JS 没有这块的优化
var superEggDrop = function(K, N) {
  // 初始化「循环不变式」相关的变量
  let cacheK = Array(N + 1)
  for (let i = 0; i <= N; i++) cacheK[i] = i
  let cacheKNext = Array(N + 1).fill(0)
  let x = 1

  // 辅助函数，用于计算 k n 已知时，单个 (k, x) 的值（x < n）
  let dropAt = (x, n) => Math.max(cacheK[x - 1], cacheKNext[n - x])

  function loop (k = 2, n = 1, x = 1, cacheK, cacheKNext) {
    // 循环终止
    if (k > K && n > N) return cacheK[N]
    // 更新 cacheKNext 与 x 以确保「循环不变式」始终成立
    while (x < n && dropAt(x, n) >= dropAt(x + 1, n)) x++
    cacheKNext[n] = 1 + dropAt(x, n)
    
    // 下一个内层循环，n 加 1
    if (n < N + 1) return loop(k, n + 1, x, cacheK, cacheKNext)
    else {
      // 更新 cacheK 与 x 以确保「循环不变式」始终成立
      cacheKNext.forEach((e, i) => cacheK[i] = e)
      // 下一个外层循环，k 加 1，n 和 x 从 1 重新开始
      return loop(k + 1, 1, 1, cacheK, cacheKNext)
    }
  }

  return loop(k = 2, n = 1, x, cacheK, cacheKNext)
}


// 迭代版循环
// 和上述递归版循环同构，「循环不变式」完全一致
var superEggDrop = function(K, N) {
  // 初始化「循环不变式」相关的变量
  let cacheK = Array(N + 1)
  for (let i = 0; i <= N; i++) cacheK[i] = i
  let cacheKNext = Array(N + 1).fill(0)
  let x = 1

  // 辅助函数，用于计算 k n 已知时，单个 (k, x) 的值（x < n）
  let dropAt = (x, n) => Math.max(cacheK[x - 1], cacheKNext[n - x])

  for (let k = 2; k <= K; k++) {
    for (let n = 1; n <= N; n++) {
      // 每一个内层循环均需更新 cacheKNext 与 x 以确保「循环不变式」始终成立
      while (x < n && dropAt(x, n) >= dropAt(x + 1, n)) x++
      cacheKNext[n] = 1 + dropAt(x, n)
    }
    // 开始下一个外层循环前，更新 cacheK 与 x 以确保「循环不变式」始终成立
    x = 1
    cacheKNext.forEach((e, i) => cacheK[i] = e)
  }
  // 循环终止：答案为 cacheK 的最后一个元素
  return cacheK[N]
}

此题还没完，还有更牛逼的解法：反过来想，有 K 个蛋，最多扔 T 次，最少能搞定多少楼层？

T 肯定 小于等于 N，递归方程也很简单，双层循环单调递增，能搞定楼层大于等于 N 时，返回此时扔的次数即可。

// 逆向思维，让递归方程变得更简单
var superEggDrop = function(K, N) {
  // 初始化「循环不变式」相关的变量
  let cache = Array(N + 1)
  // 一次不扔时，为 0
  cache[0] = Array(K + 1).fill(0)
  for (let i = 1; i <= N; i++) {
    cache[i] = Array(K + 1)
    // 没有蛋时，得零层
    cache[i][0] = 0
    // 只有一个蛋时，扔几次得几层
    cache[i][1] = i
  }
  // 只扔一次时，只要有蛋，都得 1 层
  for (let k = 1; k <= K; k++) cache[1][k] = 1
  // 从扔一次开始
  let t = 1

  finish: for (; t <= N; t++) {
    for (let k = 1; k <= K; k++) {
      // 更新 cache 以确保「循环不变式」始终成立
      cache[t][k] = 1 + cache[t - 1][k] + cache[t - 1][k - 1]
      // 判断循环是否应该终止
      if (cache[t][k] >= N) break finish
    }
  }

  // 循环终止：正确答案为 t
  return t
}