算法十分钟LeetCode1884双蛋问题

题解思路

思路一：数学公式推导

二分法是找不到的，因为只有两个鸡蛋，两次都碎了就没得用了

一种可行的做法就是用一个鸡蛋从1层开始逐层实验，但显然不是最少的步骤

根据第二个例子，采用一种很妙的阶段性枚举的方法即用第一个鸡蛋测试可能的上限，第二个鸡蛋再逐层找到。

这个例子存在的问题是它正向列出了第一个鸡蛋从9层开始实验，但不告诉你为什么从9层开始。

继续顺着这个思路思考，我们目前想做的事情是用第一个鸡蛋测试出一个上界，如果碎了，则目标一定在这层楼下面和上次测试的楼层之间。那么用第二个鸡蛋逐层测试即可。如果没碎，则继续用第一个鸡蛋找下一个可能让鸡蛋碎的上界。

最直接的想法就是我们将所有楼层平均分配，每一个均分后的楼层就是一个可能的边界。比如100层，每次都测10层。第一个鸡蛋从10层扔，下一次从20层扔，然后30层，40层。。。。

如果这样做，至少需要操作几次呢？

模拟一下，如果在第10层碎了，则第二个鸡蛋需要从1层一直试到9层（最差的情况），一共10次（第一个蛋扔了1次，第二个蛋最坏扔9次）

如果在第20层碎了，则第二个蛋需要从11层一直试到19层，一共11次（第一个扔了10层，20层两次，第二个从11到19共9次）

如果在30层碎了，则要扔12次（第一个10，20，30一共3次，第二个9次）

由此可等，最坏的情况下，到100楼还没碎，则一共测了19次（第一个扔了10次，第二个9次）

因此，在平均间隔的情况下，至少需要19次才能保证找到目标楼层

我们发现，如果固定间隔，第二个鸡蛋需要尝试的次数相同，而目标越靠后第一个鸡蛋要扔的次数就越多，导致总次数就越多。那能不能均衡一下，即前面的间隔大一些，让第二个鸡蛋多试一试，后面间隔小一些，虽然第一个鸡蛋多扔了几次，但第二个鸡蛋不需要扔太多次了。（类似一种平均期望的感觉）

顺着这个思路考虑，就能得到第二个例子的执行方式，假设第一个间隔为n，第二个间隔为n-1，第三个为n-2，依次类推，倒数第二个间隔为2，最后一个间隔就为1。我们这样倒着排回去，第一个鸡蛋最后一次在100层扔，那倒数第二个在99层扔，倒数第三个在97层扔（和上一次间隔2层），倒数第四在94层（间隔3）。以此类推，最后获得在第9层进行初次尝试（9层需要和再上一次相距14层，已经为负了，因此从这里开始）。

关键点来了，按照上面的思路，我们可以发现，每当第一个鸡蛋多扔一次，第二个鸡蛋就可以少扔一次，因此不论第一个鸡蛋在哪一层碎，总的尝试次数都是相同的，而且恰好就是这个起始的最大间隔。比如第一次尝试就碎了，那第一个鸡蛋尝试了一次，第二个鸡蛋需要尝试从1到n-1层，总共尝试就是n次。

当间隔从n开始一直递减到1，可以列出此时总楼高的计算公式为 n+n-1+n-2+n-3+…+3+2+1 = n*(n+1)/2

那我们只需要让这个计算公式大于楼层数就一定能得到目标层。

即 n*(n+1)/2 >= 100 (这里的100表示的就是楼层数，我们还是按100层举例子)

解方程再向上取整可得n=14 即100层至少测试14次可以得到结果

对应代码如下：

class Solution {
    public int twoEggDrop(int n) {
        return (int) Math.ceil((Math.sqrt(n * 8 + 1) - 1) / 2);
    }
}

思路二：记忆化递归

第二种思路是更加一般化的算法逻辑，不借助数学公式推导。

我们考虑总共有i层的楼，如果我们从其中的第j层扔下第一个鸡蛋，则有下面两种情况：

• 如果鸡蛋碎了，则第二个鸡蛋需要测试从第1层到第j-1层，那总测试次数就少1+j-1=j次

• 如果鸡蛋没碎，则我们需要测试从j到i层。而这个问题刚好等价于测试一栋有i-j层的楼的问题。因此，需要测试的次数为1+f(i-j)

上面两种情况中大的，就是一栋i层楼测试出来所要的最少次数。

用递归公式表达，对一栋i层的楼，第一个鸡蛋从j层扔下，最少需要的次数为：

$$f(j,i) = max(j,f(i-j)+1)$$

这仍旧不是最终的结果，因为第一个鸡蛋可以从1层开始，一直到i层结束，最终的结果应该是从这所有的尝试中找最小的，因此，最终的结果为：

$$F(i) = min(j=1,j=i)(max(j,f(j,i)+1))$$

代码也会有两种写法：

• 用递归的方式写，将递归调用的结果直接缓存，每次调用先查缓存，没有再计算

• 直接翻译成对应的动态规划形式

// 记忆化递归写法
class Solution {
    private static final int[] f = new int[1001];


    static {
        for (int i = 1; i < f.length; i++) {
            f[i] = Integer.MAX_VALUE;
            for (int j = 1; j <= i; j++) {
                f[i] = Math.min(f[i], Math.max(j, f[i - j] + 1));
            }
        }
    }


    public int twoEggDrop(int n) {
        return f[n];
    }
}

拓展

从2个蛋扩展到N个鸡蛋，同样可以同递归的方式来求解。详细内容请关注本公众号内的另一篇文章 [算法十分钟][LeetCode]887N蛋问题