用2个玻璃球找到从100层的大楼的某一层落下刚好会摔碎的临界层，如何制定最优策略？

有一栋100层高的大楼，给你两个完全相同的玻璃球，假设从某一层开始丢下玻璃球会摔碎，怎么利用手中的两个玻璃球，用什么最优策略（最坏情况下最少次数）知道这个临界的层是第几层？

初见

第一次看到这个题目的时候，思考了一会儿，觉得二分法可以解决这个问题，比如先尝试50楼然后尝试25楼。但转念一想，如果两次都摔碎了，岂不是根本找不到临界层了？

题目要求最坏情况下最少次数，每一种方法都要求考虑最坏情况，这种简单的二分法肯定是不行的。

其实，第一次看到这个题目时忽略了其中包含的隐性条件，导致思考的方向出现错误。

隐性条件

• 玻璃球在未摔碎的情况下可以继续使用，并增加一次尝试次数
• 必须通过这两个球获取摔碎的临界层数
• 最坏情况下的尝试次数是衡量最优策略的标准

带着这三个隐性条件再去思考，这个问题迎刃而解。

解析

默认情况下，以下尝试次数均指最坏情况下的次数

假设我们只有一个球

当我们只有一个球的时候，必须从第一层开始尝试，也就是说，需要 100 次才能找到临界层

现在我们有两个球

我们可以用第一个球去尝试，这样就可以缩小范围，至于从几楼开始尝试，这就是该问题的重点。

1. 我们假设总楼层是 total, 从第 n 楼开始尝试，尝试次数为 Worst(total, 2)
2. 如果用第一个球尝试的时候，球摔碎了，那么第二个球只能从 1 楼开始丢，尝试次数为 n
3. 如果用第一个球尝试的时候，球没有摔碎，尝试次数 +1；此时问题就变成，总楼层是 total - n, 从第 m 楼开始尝试，尝试次数为 Worst(total - n, 2)
4. 因为要求最坏情况下，所以 n 和 Worst(total - n, 2) 需要进行对比，以更大的为最坏情况下的尝试次数 Max(n, Worst(total - n, 2) + 1)
5. n 可以是 1-100, 所以还需要获得其中的最小值，也就是最优策略

\[Worst(total, 2) = Max(n, Worst(total - n, 2) + 1)\]

从以上第1条至第4条不难看出，该问题可以通过动态规划解决。

代码

const worst = total => {
  const worstObj = {}
  worstObj[1] = 1
  for (let i = 2; i <= total; i++) {
    let min = total;
    for (let n = 1; n < i; n++) {
      const result = Math.max(n, 1 + worstObj[i - n])
      min = Math.min(min, result)
    }
    worstObj[i] = min
  }
  return worstObj[total]
}

console.log(worst(100))  // => 14

根据以上代码执行结果可知：从 14 楼开始尝试，最坏情况下的最少尝试次数也是 14 次，即最优策略。有以下两种最坏情况：

14, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 96, 97, 98

参考

什么是动态规划？

2 eggs 100 floors