题目
有一栋楼共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+....+1=k(k+1)/2层扔下，只要找到最小的k，使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机会，最多测试(k-1)k/2层楼，所以第一次测试的楼层为k(k-1)/2+1,如果第一次测试没有碎，第二次增加(k-1)(k-2)/2+1层，所以三个鸡蛋，k次机会，总共能够测试的楼层为k(k-1)/2+1+(k-1)(k-2)/2+1+....+1*0/2+1=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;
两种思路总结
第一种思路是一种直接的方式，直接求解。
第二种思路是一种迂回的方式，求n个鸡蛋，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;
}
- 动态规划(1)
/**
* 动态规划
* @param floorNum 楼层数
* @param eggNum 鸡蛋数
* @return 在最怀情况下，鸡蛋最多下落的次数
*/
int getFloor(int floorNum,int eggNum){
int[][] f=new int[eggNum+1][floorNum+1];
for(int j=0;j<=floorNum;j++){
f[1][j]=j;
f[0][j]=0;
}
if (eggNum==1){
return floorNum;
}
for(int i=2;i<=eggNum;i++){
f[i][0]=0;
//从低层依次住上下落
for(int j=1;j<=floorNum;j++){
f[i][j]=0;
//计算f(eggNum,k)=f(eggNum-1,k-1)+f(eggNum-1,k-2)+....+f(eggNum-1,0)+k
for(int q=1;q<=j;q++){
f[i][j] += f[i-1][q-1];
}
f[i][j] +=j;//此处使用j,开始写成了k
//比较第一次在j层落下时，最大测试的楼层数与总楼层数
if(f[i][j]>=floorNum){
//如果超过总楼层数且等于鸡蛋数量，则返回，否则不必再计算
if(i==eggNum) {
return j;
}else{
break;
}
}
}
}
return 0;
}
- 动态规划(2）
/**
*
* @param floorNum 楼层数
* @param eggNum 鸡蛋数
* @return 最坏情况下，至多测试的次数
*/
int getFloor(int floorNum,int eggNum){
for(int i=1;i<=floorNum;i++){
if(f(eggNum,i)>=floorNum){
return i;
}
}
return 0;
}
/**
*
* @param eggNum 鸡蛋数量
* @param k K次尝试
* @return 最大测试的楼层数
*/
int f(int eggNum,int k){
int[][] f=new int[eggNum+1][k+1];
for(int j=0;j<=k;j++){
f[1][j]=j;
f[0][j]=0;
}
if (eggNum==1){
return f[1][k];
}
for(int i=2;i<=eggNum;i++){
f[i][0]=0;
for(int j=1;j<=k;j++){
f[i][j]=0;
//计算f(eggNum,k)=f(eggNum-1,k-1)+f(eggNum-1,k-2)+....+f(eggNum-1,0)+k
for(int q=1;q<=j;q++){
f[i][j] += f[i-1][q-1];
}
f[i][j] +=j;//此处使用j,开始写成了k
}
}
return f[eggNum][k];
}
测试
- 3个鸡蛋，100层楼
第二种思路-递归:第9层,耗时0ms
第二种思路-动态规划1:第9层,耗时0ms
第二种思路-动态规划2:第9层,耗时0ms
第一种思路-动态规划:第9层,耗时1ms
- 10个鸡蛋,10000层楼
第二种思路-递归:第14层,耗时0ms
第二种思路-动态规划1:第14层,耗时1ms
第二种思路-动态规划2:第14层,耗时0ms
第一种思路-动态规划:第14层,耗时478ms
- 2个鸡蛋,100000层楼
第二种思路-递归:第447层,耗时2ms
第二种思路-动态规划1:第447层,耗时2ms
第二种思路-动态规划2:第447层,耗时36ms
第一种思路-动态规划:第447层,耗时5281ms
- 60鸡蛋,10000000层楼
第二种思路-递归:第24层,耗时102ms
第二种思路-动态规划1:第24层,耗时641ms
第二种思路-动态规划2:第24层,耗时16ms
第一种思路运行中.....
可以看出，第一种思路实现方式运行是最慢的，因为需要从小到大(eggNum从2开始，floorNum从1开始)循环嵌套计算二维数组每一项的值。而第二种思路动态规划2，当得出的层数较矮时，优势明显，层数比较多时，就慢于第二种思路动态规划1，因为动态规划2，得到的结果楼层越矮时计算的越快，而动态规划1也是嵌套循环计算，但只要计算到可测试最大楼层大于或等于总楼层就停止计算，比第一种思路的动态规划要快。所以没有哪一种算法是最优的，需要根据数据量的多少来决定采取哪一种实现方法。
