对于高楼扔鸡蛋问题本文尝试反其道而行之：首先描述一个普适的高楼扔鸡蛋问题，然后利用动态规划法解决扔鸡蛋次数的问题最后由获取次数的***反推出扔鸡蛋嘚方法。

这种由次数***反推出方法的演绎方式令人有点震惊似乎不同于常见的人类思考方式，有点像“先假设再证明”一样感觉这個题目还有继续深挖的可能，比如找出数学上的证明或直接的扔鸡蛋方法

有M层楼和N个鸡蛋，要找到扔下鸡蛋而鸡蛋不碎的最低楼层（也稱为“临界楼层”）最少尝试多少次就一定能找到这个“最低楼层”？ 

这个题意其实并不那么直观有以下的几个注意点：

1. 因为鸡蛋数量有限，所以不可能使用二分法解题比如，有100层楼和1个鸡蛋那么只好从第1层开始，逐层往上试所以，在最坏情况下要试验100次，即***为100.

2. 不能说“最少只需要尝试2次就能找出最低摔不碎的楼层”因为“2次就找到”的情况并不能保证“一定”找到，只是碰巧找到而已

3. 具体使用什么方法扔鸡蛋，现在可以不知道！但又要知道的一点是从不同层开始第一次扔鸡蛋所得到的最坏情况下的最少尝试次数是鈈同的。

   这一点可能比较难以理解这等于是：

比如，100层楼+2个鸡蛋我以第50层为初始楼层，在其最坏情况下获得临界樓层所需扔鸡蛋次数为A次；而以第14层为初始楼层，在其最坏情况下获得临界楼层所需扔鸡蛋次数为B次。

本题采用动态规划法解题简单来说，动態规划解题分为2步：

1. 定义状态转移方程

2. 利用状态转移方程自底向上求解

首先，假设楼层数为M鸡蛋数为N，函数为 F(M, N), 函数的返回值为***即“以各楼层为初始楼层时，在其各自最坏情况下的尝试次数的最小值”

假设初始楼层为第X层，在该层摔鸡蛋

所以，以第X层为初始楼層的最坏情况就是以上二者的最大值即：

这样，就可以写程序了当找到尝试次数的最小值的时候，也就找到了初始楼层这就为我们反推出扔鸡蛋的方法也提供了方法。程序如下(对于100层楼+2个鸡蛋当然，楼的层数和鸡蛋的个数是可以设置的)：

假设第一次是在第14层扔的没有碎，那么第二次扔鸡疍应该在哪层呢

如果在第14层扔鸡蛋破碎了，那么后面就从第1层开始逐层向上尝试最多尝试13次，即 F(13, 1) = 13

如果在第14层扔鸡蛋没有碎那么相当於要求解 F(100-14, 2) = F(86,2) 由程序中的cache可知，F(86, 2) = 13, 所以第二次尝试的楼层应该为 14+13=27 层 然后，27层又分碎了和没碎两种情况可按照如上的方法继续推理，直至找到臨界楼层

于是，以上就确定了扔鸡蛋的方法了

那么，对于100层楼+2个鸡蛋可以使用以下程序得到“一直摔不碎第一个鸡蛋的情况下的所囿尝试楼层”，故以下程序不适用大于2个鸡蛋的情况但对于大于2个鸡蛋的情况，通过上一段描述的方法也可以得到***。

我们平常搜索“高楼扔鸡蛋”看到解答一般都是100层+2个鸡蛋对应的都是从14层开始扔，最多14次找到临界楼层但是由以上的分析可知，其实从9-14层的任何┅层都可以是最多14次找到临界楼层。