问题：100层高楼，有两个完全一样的鸡蛋，假设从某一层上扔鸡蛋，恰好会破碎。通过最优策略找到使得鸡蛋破碎的临界层需要扔多少次？

高楼扔鸡蛋常规算法

之前我们采用常规数学方法推导出该最优策略为14次。那如果把该问题扩展一下，如果有K个鸡蛋，M层楼（K∊N，M∊N），请问在最坏情况下至少需要投掷多少次？

无论是常规算法还是其他算法，我们都需要找到鸡蛋和楼层的内在联系。

一、找规律。

1.当1个鸡蛋，M层时。

答案很明显，只需要投掷M次，呈线性递增。

2. 当2个鸡蛋，一层楼时。

只需要一次，并且多于一个鸡蛋。

3. 当2个鸡蛋，2层楼时。

图1

如图所示，当只有2个鸡蛋2层楼时，第一个鸡蛋可以从第一层或者第二层投掷，又根据当前层是否破碎再次分情况讨论，最终得到如下情况：

从第一层投掷的最坏情况是2次，从第二层投掷的最坏情况是2次。

则得到一个结论：2个鸡蛋2层楼时，最坏情况下至少需要2次。

4.当2个鸡蛋3层楼时。

如图所示：

图2

当2个鸡蛋3层楼时，第一个鸡蛋分别从{1，2，3}层楼上投掷，所有的情况下，映射的最坏情况为{3，2，2}，此时在最坏情况的条件下，至少需要2次。

5.看到这里，大致能够总结出来两个规律：

①有K个鸡蛋M层楼高时，第一个鸡蛋分别从{1，2，3，.....，M}层楼投掷，考虑所有情况，映射的最坏情况对应为{A1,A2,A3....,Am},此时在最坏情况下，至少需要多少次，只需要在这个映射集合里查询。

②假设第一个鸡蛋在第i层投下，如果破碎，则破碎临界层在（1，i-1）区间，如果未破碎，则在（i+1,M）区间内。同理第二个鸡蛋在第一个鸡蛋确定的区间内继续投掷。

③由于当前状态取决于上一个状态以及如何投掷，由以上两图以及第5点的①②可看出当高楼层时将会存在大量重复的计算。

二、推论

我们规定F（K，M）表示K个鸡蛋M层楼时，最坏情况下至少投掷的次数。

假设从第i层开始投掷，根据上一个状态和规定如何投掷的方式我们可以得到一个大致的方程式：

图3

称之为状态转移方程。

其中

图4

表示上面第5点中“考虑所有情况，映射的最坏情况对应为{A1,A2,A3....,Am}”即最坏情况的集合。

图5

根据第3，4表示最坏的情况。最后加1表示第i层本身。

c++代码如下：

int F(K,M)

{

    int min_count=0;

    for(int i=1;i<=M;i++)

    {                                    min_count=min(min_count,max(F(K-1,i-1),F(K,M-1))+1);

    }

        return min_count;

    }

是不是看到递推的影子？

这就是动态规划法思想的运用。