楼层扔鸡蛋问题
有限层数和蛋数，求即使最坏情况下需要的最少判断次数
两个软硬程度一样但未知的鸡蛋，它们有可能都在一楼就摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋。
?
这是典型的动态规划问题。假设f[n]表示从n层楼找到摔鸡蛋不碎安全位置的最少判断次数。假设第一个鸡蛋第一次从第i层扔下，如果碎了，就剩一个鸡蛋，为确定下面楼层中的安全位置，必须从第一层挨着试，还需要i-1次；如果不碎的话，上面还有n-i层，剩下两个鸡蛋，还需要f[n-i]次（子问题，实体 n层楼的上n-i层需要的最少判断次数和实体n-i层楼需要的最少判断次数其实是一样的）。因此，最坏情况下还需要判断max(i-1,f[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?
?
原文地址：http://www.cnblogs.com/ltang/archive/2010/11/23/1885791.html