这道题曾经是谷歌的一道面试题，因为太过于经典，以至于谷歌取消了这道面试题。。。

1. 题目描述

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

2. 题目解析

首先要理解题目，简单意思就是给你 k 个鸡蛋去一栋 n 层楼中找出最高的一层落下鸡蛋而不破。

在数列中找目标，第一反应都会想到二分法，但仔细一想，不对，因为鸡蛋数量有限！比如说有 5 层楼 1 个鸡蛋，你怎么二分？你在 3 层楼扔下如果破了呢？你没有鸡蛋再去尝试了，所以这题单纯用二分法肯定不行。

既然一下子找不到方法，那我们先一步步分析。

假设给你 1 个鸡蛋，你怎么能找出目标楼层？简单，从第 1 层开始一层层往上试就是了，极端情况下，我们的最少操作次数就是楼层高度 n。

假设给你 2 个鸡蛋，这次又该怎么找？还是一层层往上找？肯定不合适，我们可以先用一个鸡蛋去试楼层 i，如果破了，那么目标肯定 < i，如果没破，目标肯定 >= i；最后 1 个鸡蛋再重复上面的线性扫描方式。

假设给你 3 个鸡蛋，基本重复 2 个鸡蛋的情况。先用 1 个鸡蛋去试楼层 i，如果破了，在剩下的 < i 的楼层中继续用 1 个鸡蛋去尝试楼层 j，然后最后的 1 个鸡蛋根据结果进行线性扫描。

扩展到 k 个鸡蛋，也是上述思想，用 k - 1 个鸡蛋进行区间划分尝试，最后的 1 个鸡蛋进行线性扫描。

3. 思路分析

上面的分析虽然让我们知道了解题方向，但是具体的方法，我们仍然不清楚。

这里我们不妨转换下思路，原题目是“求解找到目标 f 的最小操作次数”，如果我们换成“给你 k 个鸡蛋、t 次尝试，你能确定多少层楼落下鸡蛋而不破？”，通过递增 t 值，得到一个值，这个值刚好 >= n，那么这个 t 不就是我们要找的最少操作次数吗？

我们定义这个函数为 calc(k, t)，当你去尝试某个楼层 i，会产生两者结果，一种是蛋碎了，下一步就要下楼，继续计算能确定的楼层 calc(k -1, t -1)；另外一种是蛋没碎，我们上楼，计算式 calc(k, t -1)。

不管当前楼层蛋碎没碎，当前楼层都已经确定，然后再加上碎或者没碎的计算值，就是 k 个鸡蛋、t 次机会所能确定的最大楼层。

4. 算法实现

思路有了，剩下的就是简单的代码实现，主要要注意两点：

• 递归求值时不能忘了当前楼层，因为不管碎没碎，楼层都已经确定。
• 求解的确定楼层数一定要是大于等于 n 的最小值。

function calc(k, t) {
    // 如果只剩一个鸡蛋，只能用剩下操作的次数做线性扫描
    // 如果只剩下一次机会，那也只能确定一个楼层
    if (k === 1 || t === 1) return t
    // 分别计算当前楼层两种结果下的确定楼层数，并求和
    // 别忘了当前楼层要加1
    return calc(k - 1, t - 1) + calc(k, t - 1) + 1
}

function superEggDrop(k, n) {
    let t = 1;
    while(calc(k, t) < n) t++
    return t
}

5. 总结

这道题目真的很经典，不过通过思路转换的方式，也能用递归的方式进行求解。

不过这个解不是最优解，首先就不应该每次都从只有 1 次操作机会开始，而且 calc 的计算也存在重复计算，不过那都是进阶思考了，今天我就先到这里吧。