目录

前言

引例

数字三角形

解题思路

特点

例题

最长上升子序列

公共子序列

---

前言

第一次接触动态规划，为了更好的理解，我们首先从一道例题来讲起。

引例

数字三角形

• 题目

 

        在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。三角形的行数大于1小于等于100，数字为 0 - 99

• 输入格式

5 //三角形行数。下面是三角形

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

• 输出

最大和（30）

解题思路

        首先，比较容易想到两种解法，一种是自顶向下，还有一种就是自底向上，自顶向上，就可以使用递归来实现，而自底向上则可以使用递推来实现，我们首先来介绍一下自顶向下的解法。

自顶向下

#include  
#define MAX 101 
#define max(a,b) (((a)>(b))?(a):(b)) 
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; 
	scanf("%d", &n); 
	for(i=1;i<=n;i++) 
		for(j=1;j<=i;j++) 
			scanf("%d", &D[i][j]);
	printf("%d",MaxSum(1,1)); 
}

        使用递归实现，用二维数组存放数字三角形，然后依次递归就好了。看起来这个代码没什么问题，但如果数据过大，就会超时，原因是什么呢？我们来看看！

当我们看这个图的时候，就大概知道了，答案是重复计算 。有一些数据被重复计算了，导致时间复杂度达到了2^n。所以我们优化一下。

动规改进

#include  
#define MAX 101 
#define max(a,b) (((a)>(b))?(a):(b)) 
int D[MAX][MAX]; 
int n;
int maxSum[MAX][MAX]; 
int MaxSum(int i, int j){ 
	if( maxSum[i][j] != -1 )
		return maxSum[i][j];
	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; 
	scanf("%d", &n); 
	for(i=1;i<=n;i++) 
		for(j=1;j<=i;j++) {
			scanf("%d", &D[i][j]);
			maxSum[i][j] = -1;
		}
	printf("%d",MaxSum(1,1)); 
}

        我们采用的方法是每算出一个MaxSum(r,j)就保存起来，下次用到其值的时候直接取用，则可免去重复计算。那么可以用O(n2 )时间完成计算。

---

自底向上

        自底向上的解法也比较清晰，算出上一行到下一行的最大距离，一直往上递推，就能得到最后的答案，如下图所示。

#include  
#define MAX 101 
#define max(a,b) (((a)>(b))?(a):(b)) 
int D[MAX][MAX]; 
int n;
int maxSum[MAX][MAX]; 
int main() { 
int i,j; 
	scanf("%d", &n); 
	// 输入 
	for(i=1;i<=n;i++) 
		for(j=1;j<=i;j++) 
			scanf("%d", &D[i][j]);
	for( i = 1;i <= n; ++ i )
		maxSum[n][i] = D[n][i];
	for( i = n-1; i>= 1; --i ) 
		for( j = 1; j <= i; ++j ) 
			maxSum[i][j] =	max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j] ;
	printf("%d",maxSum[1][1]); 
}

空间优化

        空间优化，就是不再使用二维数组，而是一维数组来存储数据，因为使用二维数组存储的数据都没什么用，做的绝一点，直接用二维数组的最后一行来用，这样就能节省空间。

#include  
#define MAX 101 
#define max(a,b) (((a)>(b))?(a):(b)) 
int D[MAX][MAX]; 
int n;
int * maxSum; 
int main() { 
int i,j; 
	scanf("%d", &n); 
	// 输入 
	for(i=1;i<=n;i++) 
		for(j=1;j<=i;j++) 
			scanf("%d", &D[i][j]);
	maxSum = D[n]; //maxSum指向第n行
	for( i = n-1; i>= 1; --i ) 
		for( j = 1; j <= i; ++j ) 
			maxSum[j] =	max(maxSum[j],maxSum[j+1]) + D[i][j] ;
	printf("%d",maxSum[1]); 
}

解题思路

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

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

2. 确定状态

• 在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个“状态”。一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的解。
• 所有“状态”的集合，构成问题的“状态空间”。“状态空间”的大小，与用动态规划解决问题的时间复杂度直接相关。 在数字三角形的例子里，一共有N×(N+1)/2个数字，所以这个问题的状态空间里一共就有N×(N+1)/2个状态。
• 整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。
• 在数字三角形里每个“状态”只需要经过一次，且在每个状态上作计算所花的时间都是和N无关的常数。

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

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

4. 确定状态转移方程

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

特点

• 问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。
• 无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。
• 个人浅显的理解，动态规划与递归有相似的地方，但其特点就是将子问题的答案记录下来。然后根据子问题去求解原问题。

例题

最长上升子序列

• 题目

        一个数的序列ai，当a1 < a2 < ... < aS的时候，我们称这个序 列是上升的。对于给定的一个序列(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。

• 输出要求

最长上升子序列的长度。

• 输入样例

7

1 7 3 5 9 4 8

• 输出样例

4

解题思路

        我们采用的方法就是判断数组中每一个最长上升子序列，并且将其记录到一个数组里，在最后去找出这个数组里最大的数就行。

#include
#define max(a,b) (((a)>(b))?(a):(b)) 
#define MAXN 1010 
int a[MAXN]; 
int maxLen[MAXN];
int Max (int a[],int n){
	int max = 0,i;
	for(i = 0; i 
	{
		if(a[i]>max)
		max = a[i];
	}
	return max;
}
int main() {
int N,i,j;
	scanf("%d", &N); 
	for(i = 1;i <= N;++i) {
		scanf("%d", &a[i]) ; 
		maxLen[i] = 1;
	}
	for(i = 2; i <= N; ++i) { 
	//每次求以第i个数为终点的最长上升子序列的长度
	for(j = 1; j < i; ++j) 
	//察看以第j个数为终点的最长上升子序列
	if( a[i] > a[j] )
	maxLen[i] = max(maxLen[i],maxLen[j]+1); 
	}
printf("%d", Max(maxLen,N));
	return 0;
} //时间复杂度O(N2)

公共子序列

• 题目

        给出两个字符串，求出这样的一个最长的公共子序列的长度：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。

• 输入样例

abcfbc abfcab

programming contest

abcd mnp

• 输出样例

4

2

0

解题思路

        本题和上面的题目有点类似，都是最长子序列。但却不完全相同，首先我们看一下初始状态

MaxLen(n,0) = 0 ( n= 0…len1）
MaxLen(0,n) = 0 ( n=0…len2）

递推公式

if ( s1[i-1] == s2[j-1] ) //s1的最左边字符是s1[0]
MaxLen(i,j) = MaxLen(i-1,j-1) + 1;
else
MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) );

证明

 

 

#include
#include 
#define max(a,b) (((a)>(b))?(a):(b)) 
char s1[1000];
char s2[1000];
int maxLen[1000][1000];
int main() {
	while( scanf("%s", &s1) && scanf("%s", &s2) ) {
		int length1 = strlen( s1);
		int length2 = strlen( s2);
		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( 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]);
			}
		}
		printf("%d\n", maxLen[length1][length2]);
	}
	return 0; 
}

        好了，关于动态规划先介绍这些，后续的再慢慢介绍。