本文共 1733 字，大约阅读时间需要 5 分钟。
一幢 100 层的大楼，给你两个鸡蛋。如果在第 n 层扔下鸡蛋，鸡蛋不碎，那么从第 n-1 层扔鸡蛋，都不碎。这两只鸡蛋一模一样，不碎的话可以扔无数次。最高从哪层楼扔下时鸡蛋不会碎？
1. 如果有无数个蛋
如果问题分为两问，第一问提出如果你鹰蛋有无数个，该如何求解？这个问题比较简单，只需要二分法就能在O（lgn）的次数内求解问题，问题的第二问是如果只有两个鹰蛋，该如何求解，我当时的给的答案如下：
2.一种方案，把楼层等分试探求解
把楼层分为x等分，用第一鹰蛋从下往上依次试探一个范围，如果第一个鹰蛋破了，则用另一鹰蛋穷举。
假如将100层楼分为20等分，则用第一个鹰蛋分别在第5层，第10层，第15层。。。。依次试探，假如在35层鹰蛋破碎，则用另一个鹰蛋从31层到34层依次试探，则可以求出破蛋的临界点。
上面的方法的最坏情况是鹰蛋的临界点在N-1层（N代表总楼层数），也就是倒数第二层。因为这时候第一个蛋把所有的等分楼层都尝试了一遍，而且第二个蛋也要把一个等分内部的楼层全部尝试一遍。
假设把总楼层分成了X等份，每个等分内部有N/X个楼层。
在最坏情况下，第一个蛋需要试探X次，第二蛋则要试探N/X - 1次（即在每个等份内做穷举），所以最坏情况需要的总次数为X + (N/X) -1。
要获取最坏情况的最小值，需要对总次数X + (N/X) -1求导数，并取0值，即：
(X + (N/X) -1)'(求导)
=1- (N/X2)
=0
求解，可以得到X = sqrt(N)。
在楼层=100的情况下，可以求出使总次数最小的X=10，也就是说如果采用等份的办法，在楼层总数是100时，10等份是最优情况。
3.最终答案：动态规划
鹰蛋问题的最优解，可以通过动态规划的办法来实现，假设有m楼层，n个鹰蛋，则在第i层试探时会出现两种状态，一种状态是鹰蛋摔破了，则我们下一步只有n-1个鹰蛋，同时总楼层数也缩减为i-1，另一种状态是鹰蛋没有摔破，那么鹰蛋总数不变，还是n个，楼层数则缩减为m-i层。
这样一个问题就被分解为两个规模更小的子问题，通过递归的方式求解，递归在以下3个状态结束：1）如果鹰蛋只剩1个，那么只能对所有的楼层进行穷举；2）如果楼层是0，则需要试探0次； 3）如果楼层是1，则需要只需要试探1次。
动态规划的状态转移方程如下：
F(m,n)= MIN{ MAX{ F(i-1, n-1) + 1, F(m-i, n)+1}};(0 < i < m)
通过方程可以看出，再递归的过程中会重复的解子问题，通过array[M][N]来保存子问题的结果，提高效率，代码如下：
const int nfloor = 100;const int negg = 2;#define MAX(a, b) (a) > (b) ? (a) : (b)int arr[nfloor][negg];int test_egg(int nfloors, int neggs){ if(neggs <= 1) return nfloors; if(nfloors == 0) return 0; if(nfloors == 1) return 1; int min = nfloor; if(arr[nfloors-1][neggs-1] != 0) return arr[nfloors-1][neggs-1]; for(int i = 1; i < nfloors; i++) { int a = test_egg(i-1, neggs-1) + 1; int b = test_egg(nfloors - i, neggs) + 1; int v = MAX(a, b); if(min > v) min = v; } arr[nfloors-1][neggs-1] = min; return min;}int main(int argc, _TCHAR* argv[]){ memset(arr, 0, nfloor*negg*sizeof(int)); int a = test_egg(nfloor,negg); return 0;}