这是我面试时遇到的一个问题，后来了解到它是谷歌的一道面试算法题

问题：
已知两个鸡蛋硬度相同，100层楼。鸡蛋从f层楼房扔下时，可能会破碎。为找出使鸡蛋破碎不破碎的最高楼层f（0<f<=100），需要做x次实验，求x的最小值。

扩展问题：
M个鸡蛋，N层楼房

首先最简单的穷举，从一楼丢，直到f层

显然这是一个笨办法，也没有用上第二个鸡蛋，x可能等于100

再想到二分法

仔细想想其实这是一个有序序列中找到特定值的问题，于是我们从50层楼开始抛，但显然鸡蛋只有两个，如果第一次碎了，它也只能穷举，x可能等于50，显然二分的次数有限制。

开方

我们在二分的过程中发现，如果第一次碎了，x的最大可能值将很大，而若没碎，x的最大可能值将骤减，那么我们可以想想办法，第一抛我们选低一点，如何确定这个值呢，我们分治一下，第一个鸡蛋抛十次，第二个鸡蛋抛十次，即对100进行开方，于是x的最大可能值将等于19

降低max_x,提高min_x

显然问题需要x的最小值，我们发现开方的方法还不错，但是它的第一个鸡蛋在10层碎和100层碎的情况下，x的最大可可能值分别是11和19，仔细想想我们可以尽量抛弃运气问题，让它第一个鸡蛋无论在哪里碎，其x的最大可能值都一样，那么我们可以怎么做呢

假若从10层抛，那么为了和上次抛碎的情况下的x最大可能值相同，我们选择19层抛，依次抛。10+9+8+7+6+5+4+3+2+1 = (1+10)*10/2，于是我们就发现了楼层高度为55的最优解x为10，那么最优解为11的是66…最优解为13的是91，最优解为14的是105。

诶，好像还是不知道100层的最优解，其实想想就清楚了最优解为13的情况下是无法完成100层的求解的，而最优解为14的情况下就可以轻易的通过多种方式完成了。

那么答案就是14。

拓展

其实我们把N层楼房的答案也求了出来，
如果 (1+(x-1))_(x-1)/2 < N <= (1+x)_x/2，那么这个x就是我们要求的值了。

那如果鸡蛋为M个呢，其实这就变成一个动态规划问题了，我们思考一下：

如果鸡蛋是三个，楼层为N，怎么求x，

参考上面的思路，把新加的一个鸡蛋当成第一个鸡蛋，如果这个鸡蛋第一次在n层就碎了，这显然变成了我们之前的问题。那么只要修改第一个鸡蛋抛的间隔就可以解答这个问题了，显然这个问题的x-1等于上个问题的x，如果第一次抛的楼层为(1+(x-1))(x-1)/2+1,那么若没碎，第二次抛的跨度为(1+((x-1)-1))((x-1)-1)/2+1,那么更多鸡蛋的问题也能求出来了

（至于为什么是x-1而不是x呢，如果按照现在这个思路，把之前两个鸡蛋变成一个鸡蛋的集合，那么第一次鸡蛋抛在x=14上面碎了，单论第二个鸡蛋，其最优显然是13）

当然上述都是数学办法，当鸡蛋数量继续增大时，数学公式便可能无法表示了，但思路是可以借鉴的。我们来找通式

因为这里N是范围值，所以我们假设鸡蛋为m，最优解为x的楼高为F(x,m)

那么我们发现

  1. F(x,m)=F(x-1,m)+F(x-1,m-1)+1

那么如果 F(x-1,m)< N <=F(x,m)

就能求到x的值了，使用递归实现非常简单

  1. int F(int x, int m)
  2. {
  3.     if (m == 0 || x == 0)    return 0;
  4.     return F(x - 1, m) + F(x - 1, m - 1) + 1;
  5. }

然后for循环便能知道x为多少了，当N与m无限大时，其与x的关系是指数关系，所以时间复杂度是O(2^N*logN)

时间复杂太高了，我们优化一下。
如果画一下二叉树，会发现其类似一个杨辉三角，行高为x,但是当x<m时，杨辉三角将被截去一个角，可以直接用通项公式求出

当然这样做有些复杂，我们发现F(x,m)是由上一层的F(x-1,m)与F(x-1,m-1)决定的,那么这就是一个经典的背包问题

  1. // 优化得面目全非了，主要优化了边界问题，以及将入参修改为N
  2. // 思路还是一样的，用存上一层的数据，然后计算出下一行数据，重复如此
  3. int F(int N, int M)
  4. {
  5. // 手动填充第一行数据
  6. std::vector<int> preResult(M, 1);
  7. std::vector<int> result(M, 0);
  8. // 处理极端情况，减少循环处理逻辑
  9. if (N <= 1) return 1;
  10. if (M <= 1) return N;
  11. // 因为第一行数据被填充了，所以这里从第二行开始
  12. for (int x = 2; x <= N; ++x)
  13. {
  14.     // 填充每行的第一个数据
  15.     result[0] = x;
  16.     // 根据上一行计算出每行的数据
  17.     for (int i = 1; i < M; i++)
  18.     {
  19.         result[i] = 1 + preResult[i] + preResult[i - 1];
  20.     }
  21.     // 判断当前情况的x得出的最大值是否满足条件
  22.     if (result[M-1] >= N)
  23.         return x;
  24.     preResult = result;
  25. }
  26. }

点击关注，持续推送质量好文；如有不当，欢迎指出；转载请注明出处。