动态规划与数学方程法解决楼层扔鸡蛋问题

1.问题描述

两个软硬程度一样的鸡蛋，它们有可能都在一楼就摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置，可以摔碎两个鸡蛋，求给出一个最佳策略，测出鸡蛋恰好不会碎的楼层，最佳策略满足的条件就是在最坏情况下所扔的次数比其它任意策略的最坏情况下所扔的次数要少。并求最佳策略在最坏情况下所仍的次数。

2.问题剖析

使用一个鸡蛋我们别无选择，只有一种方案就是从一楼逐层网上试探，最坏情况下需要100次试探。但是现在使用两个鸡蛋去试探安全楼层，有很多种试探方法，比如折半试探，在大楼高度一半处的楼层50层扔第一个鸡蛋，碎了只能乖乖的用另一个鸡蛋从一楼逐层往上试，不碎的话就从51~100层的中间层75层扔第一个鸡蛋，依次类推。这种方案如果第一次在第50层楼鸡蛋碎了，第49层是安全层的话，最坏情况下需要扔50次。那么多的测试方案，我们需要找出一个最佳的测试方案，最佳体现在在最坏的情况下扔鸡蛋的次数相比其它任意策略的最坏情况下所扔的次数要少。

什么叫最坏情况，因为我们并不知道鸡蛋会在哪一个楼层首碎，所以对于任意一个测试方案都会有一个最坏的情况，最坏的情况就是试探次数最多的情况。

求解这个问题有两种办法，一种是数学方程法，一种是动态规划法。按照程序员的思路，遇到最优问题的时候，往往可以先尝试一下动态规划的方法。其次，在众多的问题当中，有不少可以直接归结为数学方程式，如果我们能够写出数学方程式，那么，答案将是更加的简洁、美妙。下面一一讲解。

3.数学方程法

假设最坏情况下最少尝试次数为x，那么，第一个鸡蛋必须要从第x层扔下，因为如果碎了，前面还有x - 1层楼需要逐层尝试，如果没碎，后面还有x-1次机会。

如果没碎，第一个鸡蛋第二次就必须从x +（x - 1）层进行尝试，为什么是加上x - 1，因为现在只剩下x-1次机会了，类比第一次扔鸡蛋，有多少次机会，就必须从第多少层开始仍。当此时，如果第一个鸡蛋碎了，第二个鸡蛋还需要从x+1 到 x + (x - 1) - 1层进行逐层尝试，有x - 2次。如果还没碎，那第一个鸡蛋，第三次从 x + (x - 1) + (x - 2)层尝试。碎或者没碎，都有x - 3次尝试机会，依次类推。那么x次的最少尝试，可以确定的最高的楼层是多少呢？ x + (x - 1) + (x - 2) + … + 1 = x(x+1) / 2 那反过来问，当最高楼层是100层，最少需要多少次呢？x(x+1)/2 >= 100, 得到x>=14，最少要尝试14次。

最佳的试探方案： 这个尝试的过程就是最佳的试探方案。具体地说，100层的楼，第一次从14层开始扔。碎了好说，从第1层开始试。不碎的话还有13次机会，再从14+13=27层开始扔，以此类推。

4.动态规划法

使用动态规划的方法求解，首要的我们要找到构成这个最优问题的最优子问题。

为什么可以用动态规划来求解这个问题呢？仔细一想，寻找100层，因为可以从1~100层之间的任意一层开始开始仍鸡蛋，假设f[n]表示从n层楼找到仍鸡蛋不碎安全位置的最少判断次数。假设第一个鸡蛋第一次从第i层扔下，那么有两种情况： 情况一：碎了，就剩一个鸡蛋，为确定下面楼层中的安全位置，必须从第一层逐层试探，还需要i-1次； 情况二：没碎，上面还有n-i层，剩下两个鸡蛋，还需要f[n-i]次。这个就是子问题了，因为实体n层楼的上n-i层需要的最少判断次数和实体n-i层楼需要的最少判断次数其实是一样的。有了子问题，我们就应该要想到动态规划。

因此，最坏情况下还需要判断max(i-1,f[n-i])次。那么对于每一个i从1到n层，尝试次数最少的，就是f[n]的值。

状态转移方程：f[n] = min{ 1+max(i-1,f[n-i]) | i=1..n } 
初始状态: f[0]=0（或f[1]=1）

有了初始状态，再根据状态转移方程递推到最终状态，最终状态就是问题的最优解。

最佳试探方案： 得到f[n]后，也就是最坏情况下最少试探次数，有了这个，就可以根据上面数学方程法中提到的试探方案得出最佳试探方案了。一旦确定了最坏情况下最少试探次数，最佳试探方案是唯一确定的，对于两个鸡蛋来说。

问题推广： 现在推广成n层楼，m个鸡蛋。两个鸡蛋可以使用数学方程法的来解决，但是对于多个鸡蛋，数学方程法就无能为力了。

还是动态规划。假设f[n,m]表示n层楼、m个鸡蛋时找到摔鸡蛋不碎的最少判断次数。则一个鸡蛋从第i层扔下，如果碎了，还剩m-1个鸡蛋，为确定下面楼层中的安全位置，还需要f[i-1,m-1]次（子问题）；不碎的话，上面还有n-i层，还需要f[n-i,m]次（子问题，实际上n层楼的上n-i层需要的最少判断次数和一个高度为n-i层楼需要的最少判断次数其实是一样的）。

状态转移方程：f[n,m]=min{ 1+max(f[i-1,m-1],f[n-i,m]) | i＝1..n } 
初始状态：f[i,0]=0，f[i,1]=i，i属于[1,n]

问题解的矩阵如下：

根据状态转移方程，逐步求出最终解f[n,m]。

具体实现：

/*********************************
@pram:high:楼层高度；eggNum:鸡蛋的数量；
@ret:最少次数
@ps:min和max为C++标准函数模板，申明在<algorithm>
*********************************/
int  eggThrowCnt(int high,int eggNum){
    int dp[32][1024]={0};

    for(int i=1;i<=high;i++)
        dp[1][i]=i;
    for(int i=1;i<=eggNum;i++)
        dp[i][1]=1,dp[i][0]=0;

    for(int i=2;i<=eggNum;i++){
        for(int j=2;j<=high;j++){
            //从k=1层开始仍，找到k=1到j层取最小值
            int k=1;                    
            int minimal=1+max(dp[i-1][k-1],dp[i][j-k]+1);   
            for(;k<=j;++k){
               minimal=min(minimal,1+max(dp[i-1][k-1],dp[i][j-k]));
            }
            dp[i][j]=minimal; 
        }
    }
    return dp[eggNum][high];
}

测试输出：

cout<<eggThrowCnt(39,3);    //输出6
cout<<eggThrowCnt(39,2);    //输出9
cout<<eggThrowCnt(36,2);    //输出8
cout<<eggThrowCnt(100,2);   //输出14
cout<<eggThrowCnt(200,2);   //输出20

多个鸡蛋（>2）的最佳试探方案： 两个鸡蛋我们通过数学推理能够得出最佳的试探方案。在多个鸡蛋的情况下，已经求出了最少试探次数的前提下，如何找到最佳的试探方案呢？

本人在网上查了很多资料，目前还是没有找到答案，也不知道这种情况下最佳试探方案是否唯一，请知道的网友留言告知，万分感谢。

参考文献

[1]楼层扔鸡蛋问题 [2]谷歌面试题——动态规划(扔鸡蛋)