本文主要是介绍[动态规划优化] 鸡蛋的硬度 状态重定义，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
有一个教授有一批一模一样的鹰蛋。有一天他来到了一栋楼的脚下，他突然想知道自己的鹰蛋从这栋楼的多少层扔下时恰好不碎。
一颗鹰蛋如果从i层摔下没有碎，那么从小于j层摔下也不会碎，如果从j层摔下碎了，从大于j层摔下也会摔碎。如果恰好存在一层n，从n层摔下鹰蛋未碎，而从n+1层摔下碎了，那么这批鹰蛋恰好从n层摔下未碎。如果从第一层摔下碎了，那么称恰好从0层摔下未碎；另一方面，如果从最高层（N层）摔下未碎，那么称恰好从N层摔下未碎
这个教授想知道从第多少层恰好摔下不碎，但是这个教授想使用最少的试验次数来得到这个值。
现已知鹰蛋的个数M和楼层高度N，试问在最坏情况下，这个教授最少需要试验多少次来得到他想要的结果？
比如：M为1，N为3。那么这个教授为了得到结果，就必须从一层一层测试，在最坏情况下，最少需要3次试验。但是如果M=2,N=3，那么他就可以第一次从二层扔下，不管碎了还是没碎，他都只需再扔一次即可得到结果，即需要做2次试验即可。
关于输入
有多组输入，每一组输入单独一行。
分别为两个如题所述的正整数N（大于0小于400001），M （大于0小于N+1）中间用空格隔开。
如果得到的N和M都为0，表示输入结束。
关于输出
每组输出单独一行，输出需要试验的次数K。
例子输入
100 1 100 2 0 0
例子输出
100 14
提示信息
动态规划，由于输入量比较大，最好尽量优化算法。
解题分析
首先介绍一种初级的方法，这种方法可以用来解决小数据的情况。我们定义一个dp数组，其中dp[i][j]表示用i个鸡蛋去测j层楼在最坏的情况下所需要测试的最少次数。
接下来，我们需要考虑如何去更新这个dp数组。首先，我们可以知道的是，如果我们手头只有一个鸡蛋，那么，在运气最差的情况下，我们不得不从第一层开始测，所以这个时候的最少次数就是楼层的层数。
如果我们只有一层楼，那么根据题意，无论我们这一下鸡蛋碎没碎，我们都可以定义这个鸡蛋的硬度了，所以这个时候我们的最少的次数就是1。
在其他情况，假定我们有m个鸡蛋需要测试n层楼，我们怎样可以得到运气最差的情况下测试所用的最少的次数呢？一个想法就是去枚举期我们所扔第一个鸡蛋的层数。我们可以假定我们第一个鸡蛋一开始从k层去扔，那么，如果碎了，我们的问题就变成是用m-1个鸡蛋测k-1层楼；如果没碎，我们的问题就变成是用m个鸡蛋去测n-k层楼。
代码实现1
#include <iostream>
using namespace std;int dp[200][200]={0};int f(int n,int m){if(dp[n][m]) return dp[n][m];if(m==1) return n;if(n==1) return 1;int res=1e9;for(int k=1;k<=n;k++){res=min(res,max(f(k-1,m-1)+1,f(n-k,m)+1));}return dp[n][m]=res;
}int main(){int n,m;while(cin>>n>>m){if(n==0 && m==0) return 0;cout<<f(n,m)<<endl;}return 0;
}当然直接用for循环打表也可以:
#include <iostream>
using namespace std;int dp[100000][100]={0};int main(){int n,m;while(cin>>n>>m){if(n==0 && m==0) return 0;for(int i=1;i<=n;i++){dp[i][1]=i;}for(int i=1;i<=n;i++)for(int j=2;j<=m;j++){dp[i][j]=i;for(int k=1;k<=i;k++){dp[i][j]=min(dp[i][j],max(dp[k-1][j-1],dp[i-k][j])+1);}}cout<<dp[n][m]<<endl;}return 0;
}解题分析2
当然，如果仅仅如此的话，还不能完美的解决本题，因为我们可以发现，N的值很大，而我们现在的这算法的时间复杂度是n^2*m，当N大于10000时，我们就会超时了。
如果去优化呢？这里需要采用状态重定义的技巧。我们发现，dp[n][m]表示m个鸡蛋测n层楼，当鸡蛋的数目一定时，我们增加楼层的数量，可以发现需要尝试的次数也会增加，也就是说，这两个量是成正比的关系，而从直观上理解，尝试的次数作为一个取min的量，其值肯定要比楼层数要小的多，所以我们可以重新定义一下dp数组的状态。
我们交换尝试的次数和楼层数的位置，dp[i][j]表示i个鸡蛋尝试j次可以到达的最大楼层数。这样，当我们发现dp[i][k-1]小于n时，说明k-1次不能测出鸡蛋的硬度，且我们发现dp[i][k]>=n，那么我们要求的次数就是k次。（相当于对我们之前那个过程的逆向处理）。
于是dp[i][j]=dp[i-1][j-1]（有可能鸡蛋碎了，那就测下面的楼层）+dp[i][j-1]（有可能鸡蛋没碎，那就测上面的楼层）+1（当前的这个楼层）。
代码实现
#include <iostream>
#define Max_trial 100
#define MaxM 400005
using namespace std;int dp[MaxM][Max_trial]={0};int main(){int n,m;for(int i=0;i<Max_trial;i++){dp[1][i]=i;}for(int i=2;i<MaxM;i++)for(int j=1;j<Max_trial;j++){dp[i][j]=1+dp[i][j-1]+dp[i-1][j-1];}while(cin>>n>>m){if(n==0 && m==0) return 0;if(m==1) {cout<<n<<endl;continue;}for(int i=0;i<Max_trial;i++){if(dp[m][i]>=n){cout<<i<<endl;break;}}}return 0;
}这篇关于[动态规划优化] 鸡蛋的硬度 状态重定义的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
