这是经典的谷歌面试题，也是经典的动态规划问题
根据y总的说法，动态规划问题要划分集合，表示状态
对于这道题，有两个经典的解法，他们的复杂度不同，因为对状态的定义略有不同
1.最常规的思想，设计状态为前i层用j个鸡蛋所能测的最坏情况的最小值是多少
我相信集合的定义很多人能想到，但是状态的定义还需要进行分析
首先，为什么是最坏情况，因为我们不知道鸡蛋什么时候会碎，这是未知的，所以要考虑最坏的情况，而最小值是因为，这是我们能控制的。
所以不能控制的要考虑最坏，能控制的要考虑最好
那么状态转移方程就能定义为f[i][j-1]和max(f[i-k][j],f[k-1][j-1]]+1中的最小值，因为我们在考虑测试的时候，可以在1-i中任选一个地方开始测，但是我们不能知道在我们选的地方蛋会不会碎
另外，还可以不适用鸡蛋，也就是直接沿用f[i][j-1]的情况
#include<iostream> #include<algorithm> using namespace std; const int N=1010; int f[N][N]; int main(){ int i,j; int n,m; while(cin>>n>>m){ for(i=1;i<=n;i++){ f[i][1]=i; } for(i=1;i<=m;i++){ f[1][i]=1; } for(i=2;i<=n;i++){ for(j=2;j<=m;j++){ f[i][j]=f[i][j-1]; int k; for(k=1;k<=i;k++){ f[i][j]=min(f[i][j],max(f[i-k][j],f[k-1][j-1])+1); } } } cout<<f[n][m]<<endl;} }
2.上面的复杂度比较高，那是因为我们要选一个地方进行测试，所以要多枚举一维。第二种方法更加巧妙
我们定义f[i][j]为用j个鸡蛋测量i次最多能测多长的区间，我们能想到这个状态的原因是，动态规划的划分依据一般从题目所给信息想出，我们既然不想枚举位置，那么就把长度当作状态量，而把次数和个数当作状态。
这样的话就能用f[i-1][j-1]+f[i-1][j]+1,这个意思是，如果蛋碎了，那就是测i-1次用j-1个鸡蛋的长度，不然就是i-1次用j个鸡蛋的长度，因为蛋的情况只有一种，所以两个集合独立，可以相加，而他们相加就是最终的答案
#include<iostream> #include<algorithm> using namespace std; const int N=1010; int f[N][N]; int main(){ int i,j; int n,m; while(cin>>n>>m){ for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ f[i][j]=f[i-1][j]+f[i-1][j-1]+1; } if(f[i][m]>=n){ cout<<i<<endl; break; } } } }