有一栋楼共N层，一个鸡蛋从第M层及以上的楼层落下来会摔破， 在第M层以下的楼层落下不会摔破。给你Q个鸡蛋，设计方案找出M，并且保证在最坏情况下， 最小化鸡蛋下落的次数。
这道题目经常在面试中问到，很多博客也给出了答案，但总感觉不全面，没有讲透彻，依据前人经验和自己的理解，从思路和实现两个方面进行思考，看一看采取哪一种算法合适。
为了简化问题，先假定有2个鸡蛋，100层楼。
假设最坏情况下，至多仍k次，那第一次需要在第k层仍下，会有两种情况：
碎了。这时只剩下一个鸡蛋，只能从1层，一层层往上仍，最坏情况下仍到第k-1层，如果在k-1层碎了，那N=k-1,总共仍了k次，如果没碎，那N=k，总共也仍了k次。
没碎。这时手上还有2个鸡蛋，从k+1层开始往下仍，还可以仍k-1次，1到k层，最多仍k次，k-1次最多仍k-1层，所以第二次在k+k-1层往下扔，如果第二次仍没碎，第三次在k+k-1+k-2=3k-3层上仍，依此类推。
所以得出，2个鸡蛋的时候，k次机会，最多可以从\(k+k-1+k-2+k-3+....+1 = \frac{k(k+1)} {2}\)层扔下，只要找到最小的k，使$\frac{k(k+1)} {2} >= 100 $，就找到了第一次扔的k层,容易得到k=14。
这样就能保证在找到M时，扔的次数最多不超过14次。
假设f[n][m]表示n个鸡蛋，m层时，最坏情况下,至多扔的次数(f是一个二维数组)。
\(f[2][100]=1+max(f[1][k-1],f[2][100-k];(k为第一次仍的楼层)\)
常数1表示第一次在k层仍下了一个鸡蛋。
f[1][k-1]表示当第一次在k层仍下第一个鸡蛋时，碎了，还剩一个鸡蛋，只能在k-1层楼范围扔了。
f[2][100-k]表示第一次在k层仍下第一个鸡蛋时没有碎，那么还剩下2个鸡蛋，100-k层楼。
如果有3个鸡蛋，100层楼时，\(f[3][100]=1+max(f[2][k-1],f[3][100-k]);\)
可以类推得到\(f[n][m]=1+max(f[n-1][k-1],f[n][m-k])\)
上面已经得到2个鸡蛋，k次机会，最多可以测试k(k+1)/2层楼。
假如有3个鸡蛋，k次机会，第一次测试碎了后，只剩下k-1次机会，必须要把剩下的楼层测试完。2个鸡蛋，k-1机会，最多测试\(\frac{(k-1)k} {2}\)层楼，所以第一次测试的楼层为\(\frac{k(k-1)} {2}+1\),如果第一次测试没有碎，第二次增加\(\frac{(k-1)(k-2)} {2}+1\)层，所以三个鸡蛋，k次机会，总共能够测试的楼层为\[\frac{k(k-1)} {2}+1+ \frac{(k-1)(k-2)} {2}+1+....+\frac{1*0} {2}+1 = \frac{k^3+5k} {6}\]。
总结：
用f(n,k)表示n个鸡蛋，第一次在k层楼时，最多扔的楼层数(f是一个函数)。
\(f(1,k)=k;\)
\(f(2,k)=f(1,k-1)+f(1,k-2)+....+f(1,0)+k;\)
\(f(3,k)=f(2,k-1)+f(2,k-2)+f(2,k-3)+....+f(2,0)+k\)
\(……\)
\(……\)
\(f(n,k)=f(n-1,k-1)+f(n-1,k-2)+....f(n-1,0)+k;\)
自己对于java最熟悉，就使用java进行编码
先给出两种思路的实现代码，最后再解释。代码中省略对楼层和鸡蛋数量有效性的检查。
第一种思路这一种思路是大多数博客常用的思路，解法也都是动态规划，这里仍然使用动态规划。
动态规划
int getFloor(int floorNum,int eggNum){ if(eggNum < 1 || floorNum < 1) return 0; //f二维数据存储着eggNum个鸡蛋，从floorNum楼层扔下来最怀情况下，所需最多的次数 int[][] f = new int[eggNum+1][floorNum+1]; for(int i=1;i<=eggNum; i++){ for(int j=1; j<=floorNum; j++) f[i][j] = j;//初始化，最坏的次数 } for(int n=2; n<=eggNum; n++){ for(int m=1; m<=floorNum; m++){ for(int k=1; k<m; k++){ f[n][m] = Math.min(f[n][m],1+Math.max(f[n-1][k-1],f[n][m-k])); } } } return f[eggNum][floorNum]; } 第二种思路这一种思路，考虑使用递归和动态规划,动态规划用了两种方式实现。
递归(1)
/** * 递归 * @param floorNum 楼层数 * @param eggNum 鸡蛋数 * @return 在最怀情况下，鸡蛋最多下落的次数 */ int getFloor(int floorNum,int eggNum){ //从1层依次往上计算最大测试楼层 for(int i=1;i<=floorNum;i++){ if(maxFloor(eggNum,i)>=floorNum){ return i; } } return 0; } /** * eggNum鸡蛋,k次尝试最大能测试的楼层数 * @param eggNum 鸡蛋数量 * @param k 尝试次数 * @return 最大测试的楼层数 */ int maxFloor(int eggNum,int k){ //f(1,k)=k if (eggNum==1) return k ; int result=0; //计算f(eggNum,k)=f(eggNum-1,k-1)+f(eggNum-1,k-2)+....f(eggNum-1,0)+k for(int i=0;i<k;i++){ result += maxFloor(eggNum-1,i); } result += k; return result; }