目录
第一次接触动态规划,为了更好的理解,我们首先从一道例题来讲起。
在上面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可,不必给出具体路径。三角形的行数大于1小于等于100,数字为 0 - 99
5 //三角形行数。下面是三角形 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
最大和(30)
解题思路
首先,比较容易想到两种解法,一种是自顶向下,还有一种就是自底向上,自顶向上,就可以使用递归来实现,而自底向上则可以使用递推来实现,我们首先来介绍一下自顶向下的解法。
自顶向下
#include <stdio.h>
#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 <stdio.h>
#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 <stdio.h>
#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 <stdio.h>
#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. 确定状态
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<stdio.h>
#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 <n;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<stdio.h>
#include <string.h>
#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;
}
好了,关于动态规划先介绍这些,后续的再慢慢介绍。