本文主要是介绍浅谈动态规划优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
动态规划是解决多阶段决策最优化问题的一种思想方法。
有时动态规划的时间复杂度过高，需要我们对动态规划进行优化。
对动态规划进行优化的普遍方法是重新定义阶段，我们用一个例子来加以说明：
鹰蛋问题：
有一堆共 M 个鹰蛋，一位教授想研究这些鹰蛋的坚硬度 E。他是通过不断从一幢 N 层的楼上向下扔鹰蛋
来确定 E 的，当鹰蛋从第 E 层楼及以下楼层落下 时是不会碎的，但从第（E+1）层楼及以上楼层向下落时会摔碎。
如果鹰蛋未摔碎，还可以继续使用，但如果鹰蛋全碎了却仍未确定 E，这显然是一个失败的实验。教授希望实验是成功的
这里假设所有的鹰蛋都具有相同的坚硬度。给定鹰蛋个数 M 与楼层数 N。 要求最坏情况下确定 E 所需要的最少次数；
分析这个问题可以知道它是求一个最优值，那么我们很自然想到用动态规划来做题。
可以发现这个问题的阶段还是比较明显的。可以根据鹰蛋数和楼层来划分阶段
定义状态：定义状态dp[i][j]是当i个鹰蛋在长度为j的楼上最坏情况下确定E所需要的最少次数。
比如dp[3][5]是指3个鹰蛋在楼层数为5的楼上最坏情况下确定E所需要的最少次数。
状态转移：在进行状态转移的时候，我们可以从两方面来考虑，一是考虑该状态可以由什么状态转移过来。如果这方面
不容易想的话，可以考虑这个状态可以想什么状态转移。具体到这个问题，我们在楼层数为j的楼上测试i个
鹰蛋有j个决策，分别是从第1层扔下，从第2层扔下......从第j层扔下。每次扔下都有两个情况。
假设鹰蛋再第k层扔下(1<=k<=j)：
1. 鹰蛋没碎：如果鹰蛋没碎，那么在楼层数为k-1个楼上测试i个鹰蛋在最坏情况下的最少次数再加上本次测
试就是dp[i][j]的值。
2. 鹰蛋碎了：如果鹰蛋碎了，那么在楼层数为j-k个楼上测试i-1个鹰蛋在最坏情况下的最少次数再加上本次测
试就是dp[i][j]的值。
因为题目要求在最坏情况下，所以我们要在两种情况中选一个最大值，又要求最少次数所以要在j个决策中选
一个值最小的。
所以状态转移方程为dp[i][j] = min{ max{ dp[i-1][j-k], dp[i][k-1] } + 1 | 1<=k<=j };
按一个方向求出该问题的解： 根据状态转移方程，可以看出如果我们要得出dp[i][j]的值，我们要得出dp[i-1][]的值和
dp[i][k-1](k <= j)的值。所以i应该在外循环，从小到大。j应该在内循环，从小到大。
代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a))
using namespace std;const int INF = 999999999;int dp[55][10005]; //定义状态 /*
2 10
2 100
2 300
25 900
Sample Output
4
14
24
10
*/int main()
{int n,m;while(~scanf("%d%d",&n,&m)) {mmset(dp,0);for(int i = 1; i <= m; i++) //初始化 dp[1][i] = i;for(int i = 2; i <= n; i++) //状态转移方程 ，自底而上的求解 {for(int j = 1; j <= m; j++){dp[i][j] = INF;for(int k = 1; k <= j; k++){dp[i][j] = min(max(dp[i-1][k-1],dp[i][j-k]) + 1,dp[i][j]);}}}printf("%d\n",dp[n][m]);}return 0;
}
这篇关于浅谈动态规划优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
