题目：

给你 n 个鸡蛋，和一栋从 1 到 m 共有 m 层楼的建筑。

你需要测试鸡蛋的耐摔度  也就是鸡蛋从第几层扔下去恰好会碎

如果鸡蛋的耐摔度是 F   那么任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

你每次测试可以拿一个鸡蛋，把它从任意高度的楼层 扔下（没摔碎的话 还可以继续使用）

你的目标是测试出 F 的值是多少。要求在最坏的情况下  用尽量少的测试次数来找到鸡蛋的耐摔度

 

解题思路：

1、首先我们要理解题目意思，根据题意，我们很容易想到一种完成任务的笨方法，那就是拿一个鸡蛋，从一楼开始慢慢的往上层测试。这个方法可以只用一个鸡蛋就能找到耐摔度。但是需要的测试次数最大是N（如果N层也摔不碎 那你需要n次）

2、如何优化次数呢？可能很容易联想到二分查找，

我们假设有100层楼，给你两个鸡蛋。

用二分查找的话，我们首先在第50层楼扔，如果鸡蛋不碎的话，到第75层扔。如果50层碎了的话，那么你只剩下一个鸡蛋了，所以你不能浪了，只能使用第一个思路，从第一层开始慢慢往上找，这样才能保证你能找到临界楼层。

题目上说了，要我们考虑最坏情况下的最小次数，那么用二分查找的话，最坏情况就是如果临界层数在49层的话，我们要尝试50次。这个方法并不是最优秀的方法。

3、dp

先假设情况：2个鸡蛋，100层楼，求最坏的情况下，需要最少几次次测试才能找到鸡蛋的耐摔度

我们假设答案是x.（最坏需要x次）

然后我们首先在第x层扔鸡蛋  会有两种结果

1、碎了   若碎了 剩下的一个鸡蛋只能从1-（x-1）遍历尝试了

2、没碎  若没碎  那么第二次就在x+(x-1)楼层摔。

为什么是x+x-1楼层呢？
首先我们已经假设了通过x步我们就能得到答案，现在我们在x层已经用了一次了，那么就只剩下x-1步了。

所以我们选择x+(x-1)层，如果碎了，我们就能通过x-2步，遍历x+1 ~  x+(x-1)-1的所有楼层。

 依次类推。

如果在x+(x-1)楼碎了，那么同1，遍历x+1~x+(x-1)-1
如果没碎，那么同2，就在x+(x-1)+(x-2)层摔

.....................................

 可以看到，每次我们增加的楼层都是前一次减1.所以我们还要保证的就是应该在增加的层数变成0之前到顶楼，

所以有： x+(x-1)+…+1≥100

等差数列  求和之后  可以化简为 x^2+x-200≥0   解出来  x是14  

显然  14比我们二分的最坏情况50次要少   这就是正确答案。

 

那么  现在跳出我们假设的题目  推一下普适的方法

n个鸡蛋，m层楼

f[ n ][ m ]代表  最坏的情况下，找到鸡蛋的耐摔度需要的最小次数

状态转移方程为：f[n][m] = min {  1 + max ( f [ n-1 ][ k-1 ] , f [ n ][ m-k ] )  }         k属于[1,m-1]

为什么是这样呢？

我们一层一层来看  先看内层

max ( f [ n-1 ][ k-1 ] , f [ n ][ m-k ] )

n个鸡蛋的时候，我们选择第k层往下摔

如果破了，那么手里只有n-1鸡蛋了，那么就需要测试f[n-1][k-1]楼层。

如果没破，那么手里还有n个鸡蛋，那么需要测试k+1 ~ m这些楼层。也就是f[n][m-k]。

而无论破没破  都算一次测试了  所以不管破没破 都要 + 1

而为什么取最大值呢？因为题目说了 要最坏情况  所以我们取这两者中步数多的

而k怎么选呢    再看总的式子

f[n][m] = min {  1 + max ( f [ n-1 ][ k-1 ] , f [ n ][ m-k ] )  }         k属于[1,m-1]

    k的选取范围是[1,m-1]   而我们目的是想测试次数最少   所以我们在这里面选一个会使结果最小的k值  所以外边枚举k，取min

 

至此  整个思路就完成了

初始话的时候  给整个二维数组都初始化为最坏情况  然后dp就好了

ps：补充一点  max ( f [ n-1 ][ k-1 ] , f [ n ][ m-k ] )  有人认为没必要选最大  越高层越容易碎  所以直接选低层

这是不对的  要注意 确实越高层越容易碎  但是我们要求的是次数最小  跟碎不碎没关系  碎不碎都要算次数的  如果你想不碎 那直接从一层开始  一个鸡蛋就够了  所以 要明白我们要求的是什么

代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
const int INF=0x3f3f3f3f;
int a[105][10005];
int n,m,minn;
int main(){
    for(int i=1;i<=100;i++){//初始化
        for(int j=1;j<=10000;j++){
            a[i][j]=j;
        }
    }
    scanf("%d%d",&n,&m);//n个鸡蛋  m层楼
    for(int i=2;i<=n;i++){
        for(int j=2;j<=m;j++){
            for(int k=1;k<=j-1;k++){
                a[i][j]=min(a[i][j],1+max(a[i-1][k-1],a[i][j-k]));
            }
        }
    }
    printf("%d\n",a[n][m]);
}


参考文档：

https://blog.csdn.net/wolinxuebin/article/details/47057707

http://www.cnblogs.com/Matrix_Yao/p/4793823.html