[数据结构与算法]程序设计与算法--动态规划

动态规划在我们解题时十分重要，动态规划的思想其实很容易掌握，只要是学会怎样去灵活运用，把题目给出的条件进行拆解，得到“最优子结构”以此来得到递归公式，当然既然用到了递归，减枝也是非常的重要，我们同样也可以把递归转化为递推型。

目录

引例

递归型

改进

递推型

改进

动规解题方法

例题

最长上升子序列

引例

这时1994 年的 IOI（国际信息学奥林匹克竞赛）的?The triangle，时光飞逝，经过20多年的积淀，往日的国际竞赛题现如今已经变成了动态规划的入门题，不断的督促着我们学习和巩固算法。

现在让我们回过来看这道题，题意是在上面的数字三角形中寻找一条从顶部到定边的路径，使得路径上经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出路径。三角形的行数大于1小于等于100，数字为0-99。

输入格式：

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

要求输出最大和

递归型

解题思路：

D(r,j) : 第r行第j个数字（r,j从1开始算）

MaxSum（r,j）:从D(r,j)到底边的各条路径中，最佳路径的数字之和。

问题：求MaxSum(1,1)

典型的递归问题。D(r,j)出发，下一步只能走D(r + 1,j)或者(r + 1,j + 1)。故对于N行的三角形：

if(r == N)

? ? ?MaxSum(r,j) = D(r,j)

else

? ? MaxSum(r,j) = Max{MaxSum(r + 1,j),MaxSum(r + 1,j + 1)} + D(r,j)

#include<iostream>
#include<algorithm>
#define MAX 101
using namespace std;
int D[MAX][MAX];//定义二维数组储存三角形    
int n;
int MaxSum(int i,int j){
	if(i == n)//如果遍历到最底部    
	return D[i][j];
	int x = MaxSum(i + 1,j);//向下
	int y = MaxSum(i + 1,j + 1);//向右下
	return max(x,y) + D[i][j];
}
int main()
{
	int i,j;
	cin >> n;
	for(i = 1;i <= n;i++){
		for(j = 1;j <= i;j++){
			cin >> D[i][j];
		}
	}
	cout << MaxSum(1,1) << endl;//从最上角遍历数组
 } 

该算法为从下到上累加并记录的算法，依照此解法虽然可以得到最后的结果，但由于计算每一步时，都要计算从最下面一层到该位置的最小总和，所以存在大量的重复计算，在一些oj平台上面很容易超时。

时间复杂度过高，我们需要进一步优化。

改进

我们根据问题可以考虑到，算法超时是因为大量重复计算，如果每算出一个MaxSum(r,j)就保存下来，下次用到其值的时候直接取用，则可免去重复计算。那么可以用O()时间完成计算。因为三角形的数字总和为n(n + 1) / 2。

#include<iostream>
#include<algorithm>
#define MAX 101
using namespace std;
int D[MAX][MAX];
int maxSum[MAX][MAX];//储存每一步的MaxSum
int n;
int MaxSum(int i,int j){
	if(maxSum[i][j] != -1)return maxSum[i][j];//已经记录下MaxSum值
	if(i == n)maxSum[i][j] = D[i][j];//最底层
	else{
		int x = MaxSum(i + 1,j);
		int y = MaxSum(i + 1,j + 1);
		maxSum[i][j] = max(x,y) + D[i][j];
	}
	return maxSum[i][j];
}
int main()
{
	int i,j;
	cin >> n;
	for(i = 1;i <= n;i++){
		for(j = 1;j <= i;j++){
			cin >> D[i][j];
			maxSum[i][j] = -1;//初始化每一个值
		}
	}
	cout << MaxSum(1,1) << endl;
}

递推型

当然这道题既然可以用递归形式，我们也可以转化为递推，递归转递推就是按照递归的思路来拆解，我们可以知道从底层向上计算，所以我们可以用一个二维数组来储存每一步从下到上的相加起来的值，然后根据要求返回。

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 101
int maxSum[MAX][MAX];//储存每一步数组的值 
int main()
{
	int i,j;
	cin >> n;
	for(int i = 1;i <= n;i++)
	for(int j = 1;j <= i;j++)
	cin >> D[i][j];
	for(int i = 1;i <= n;i++)
	maxSum[n][i] = D[n][i];//赋值最底层
	for(int i = n - 1;i >= 1;i--)
	for(int j = 1;j <= i;j++)
	maxSum[i][j] = max(maxSum[i + 1][j],maxSum[i + 1][j + 1]) + D[i][j];//计算每一步的和
	cout << maxSum[1][1] << endl;
}

改进

我们可以进一步考虑，直接用最后一行的数组来进行储存数据，当然我们可以直接原地进行修改，因为该题的无后效性。

#include<iostream>
#incldue<algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n; 
int *maxSum;
int main()
{
	int i,j;
	cin >> n;
	for(i = 1;i <= n;i++)
	for(j = 1;j <= i;j++)
	cin >> D[i][j];
	maxSum = D[n];//指向最后一行
	for(int i = n - 1;i >= 1;--i)
	for(int j = 1;j <= i;++j)
	maxSum[j] = max(maxSum[j],maxSum[j + 1]) + D[i][j];
	cout << maxSum[1] <<endl;
 } 

动规解题方法

根据上面的动规入门题，我们可以总结出动规的一般思路，即从递归到动规的转化方法。

递归函数有n个参数，就定义一个n维数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界值开始逐步填充数组，相当于计算递归函数值的逆过程。

动规解题的一般思路

1.将原问题分解为子问题

• ? 把原问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决，原问题即解决（数字三角形例）。
• 子问题的姐一旦求出就会被保存，所以每个子问题只需求解一次。

2.确定状态

• ?在用动态规划解题时，我们往往将和子问题相关的每个变量的一组取值，称之为一个“状态”。一个“状态”对应于一个或多个子问题，所谓某个“”“状态”下的“值”，就是这个“状态”所对应的子问题的解。
• 用动态规划解题，经常碰到的情况是，K个整型变量能构成一个状态（如数字三角形中的行号和列号这两个变量构成“状态”）。如果这K个整型变量的取值范围分别是N1，N2，……Nk，那么，我们就可以用一个K维的数组array[N1][N2]……[Nk]来储存规格状态的“值”。这个“值”未必就是一个整数或浮点数，可能是需要一个结构才能表示的，那么array就可以是一个结构数组。一个“状态”下的“值”通常会是一个或多个子问题的解。

3.确定一些初始状态（边界状态）的值

? ? ? ?以“数字三角形”为例，初始状态就是底边数字，值就是底边数字值。

4.确定状态转移方程

? ? ? ?定义出什么是“状态”，以及在该“状态”下的“值”后，就要找出不同的状态之间如何迁移——即如何从一个或多个“值”已知的“状态”，求出另一个“状态”的“值”（“人人为我”递推型）。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。

? ? ? ?数字三角形的状态转移方程：

?

?能用动规解决的问题的特点

1. 问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称为该问题具有最优子结构性质。
2. 无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过那条路径演变到当前的这若干个状态，没有关系。

例题

最长上升子序列

一个数的序列bi，当b1?<?b2?< ... <?bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,?a2, ...,?aN)，我们可以得到一些上升的子序列(ai1,?ai2, ...,?aiK)，这里1 <=?i1?<?i2?< ... <?iK?<= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入：

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

输出：

最长上升子序列的长度。

?解题思路：

1.找子问题

? ?“求序列的前n个元素的最长上升子序列的长度”是个子问题，但这样分解子问题，不具有“无后效性”

? ?假设F(n) = x，但可能有多个序列满足F(n) = x。有的序列的最后一个元素比小，则加上就能形成更长上升子序列；有的序列最后一个元素不比小……以后的事情受如何达到状态n的影响，不符合“无后效性”。

? ?“求以(k = 1,2,3...N)为终点的最长上升子序列的长度”

? ?一个上升子序列中最右边的那个数，称为该子序列的“终点”。

? ?虽然这个子问题和原问题的形式上并不完全一样，但只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。

2.确定状态：

? ?子问题只和一个变量--数字的位置相关。因此序列中数的位置k就是“状态”，而状态k对应的“值”，就是以做为“终点”的最长上升子序列的长度。

? ?状态一共有N个。

3.找出状态转移方程：

? ?maxLen(k)表示以做为“终点” 的最长上升子序列的长度那么：

? ?初始状态：maxLen(1) = 1

? ? ? ?maxLen(k) = max{maxLen(i):1 <= i < k且 ?<?且k? <> 1} + 1

? ? ? ? ? ? ? ? ? ? ?若找不到这样的i，则maxLen(k) = 1

? ?maxLen(k)的值，就是在左边，“终点”数值小于，且长度最大的那格上升子序列的长度再1。因为左边如何“终点”小于的子序列，加上后就能形成一个更长的上升子序列。

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int MAXN = 1010;
int a[MAXN];
int maxLen[MAXN];
int main()
{
	int N;  cin >> N;
	for(int i = 1;i <= N; ++i){
		cin >> a[i]; maxLen[i] = 1;
	}
	for(int i = 2;i <= N;++i){//每次以i为终点的最长上升子序列长度
		for(int j = 1;j < i;++j){//以第j个数为起点
			if(a[i] > a[j])//右边大于左边
			maxLen[i] = max(maxLen[i],maxLen[j] + 1);
		}
		
	}
	cout << * max_element(maxLen + 1,maxLen + N + 1);//数组中取最大的
		return 0; 
}

?动规的常用两种形式：

1. 递归型

? ? ? ? ?优点：直观，容易编写

? ? ? ? ?缺点：可能会因递归层数太深导致爆栈，函数调用带来额外时间开销。无法使用滚动数组节省空间。总体来说懵逼递推型慢。

? ? ? 2.递推型

? ? ? ? ?效率高，有可能使用滚动数组节省空间。

最长公共子序列：

给定序列的子序列是省略某些元素（可能没有元素）的给定序列。给定一个序列 X = < x1， x2， ...， xm >另一个序列 Z = < z1， z2， ...， zk > 如果存在一个严格递增的序列< i1， i2， ...， ik > X 的索引，使得对于所有 j = 1，2,...,k， x i j = zj， xij?= zj。例如，Z = < a， b， f， c > 是 X = < a， b， c， f， b， c > 的子序列，索引序列< 1，2，4，6 >。给定两个序列 X 和 Y，问题是找到 X 和 Y 的最大长度公共子序列的长度。

输入：

程序输入来自标准输入。输入中的每个数据集都包含两个表示给定序列的字符串。序列由任意数量的空格分隔。输入数据正确。

输出：

对于每组数据，程序在标准输出上打印从单独行的开头开始的最大长度公共子序列的长度。

题解思路：?

输入两个串s1，s2，设MaxLen（i,j）表示：

? ?s1的左边i个字符形成的子串，与s2左边的j个字符形成的子串的最长公共子序列的长度（i，j从0开始算） MaxLen（i，j）就是本题的“状态”

假设len1 = strlen(s1),len2 = strlen(s2)

那么题目就是要求 MaxLen(len1,len2)

显然：

MaxLen(n,0) = 0? ? ? ? MaxLen(0,n) = 0

递推公式:??

if(s1[i - 1] == s2[j - 1])? MaxLen(i,j) = MaxLen(i - 1,j - 1) + 1;

else MaxLen(i,j) = Max(MaxLen(i,j - 1),MaxLen(i - 1,j));

时间复杂度O(mn) m，n是两个字串长度

?S1[i - 1] != S2[j - 1]时，MaxLen(S1,S2)不会比和MaxLen(,S2)两之中如何一个小，也不会比两者都大。

#include<iostream>
#include<cstring>
using namespace std; 
char sz1[1000];
char sz2[1000];
int maxLen[1000][1000];
int main()
{
	while(cin >> sz1 >> sz2){//读入数据
		int length1 = strlen(sz1);
		int length2 = strlen(sz2);
		int nTmp;
		int i,j;
		for(i = 0;i <= length1;i++)//初始化边界
		maxLen[i][0] = 0;
		for(j = 0;j <= length2;j++)
		maxLen[0][j] = 0;
		for(i = 1;i <= length1;i++){
			for(j = 1;j <= length2;j++){
				if(sz1[i - 1] == sz2[j - 1])
				maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
				else
			    maxLen[i][j] = max(maxLen[i][j - 1],maxLen[i - 1][j]);
			}
		}
		cout << maxLen[length1][length2] << endl;
	}
	return 0;
}