算法设计与分析第4章 动态规划(二)【DP序列问题】
第3章 动态规划(二)【DP序列问题】
3.2 DP序列问题
(51nod的动态规划教程很不错,讲解很详细,以下分析来自51nod)
1.矩阵取数问题
给定一个m行n列的矩阵,矩阵每个元素是一个正整数,你现在在左上角(第一行第一列),你需要走到右下角(第m行,第n列),每次只能朝右或者下走到相邻的位置,不能走出矩阵。走过的数的总和作为你的得分,求最大的得分。
分析:
从起点到终点的最优路径上经过了(m + n – 1)个点,则这条路径上对应起点到这(m + n – 1)个点的子路径也都从起点到该位置的所有路径中和最大的路径。
定义f(int x,int y)表示从起点到第x行第y列的最优路径上的数之和,有从起点达到x,y的最优路径有两种可能:
要么f(x – 1, y) + A[x][y]
要么f(x, y – 1) + A[x][y]
所以,f(x, y) = max(f(x – 1, y) , f(x, y – 1) ) + A[x][y]
初值:
f(1,1)是起点,没的选f(1,1) = A[1][1]。
按照递推式 f(1,2) = max(f(0, y) , f(1,1)) + A[1][2],考虑实际意义,这表示要么从上面到达(1,2)要么从左面到达(1,2),可是上面没有位置,说明没的选。所以可以定义f(0, y) = -∞, 同理f(x, 0) = -∞。
递推式:
输入
第1行:N,N为矩阵的大小。(2 <= N <= 500)
第2 - N + 1行:每行N个数,中间用空格隔开,对应格子中奖励的价值。(1 <= N[i] <= 10000)
输出
输出能够获得的最大价值。
输入示例
3
1 3 3
2 1 3
2 2 1
输出示例
11
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int n,i,j;
int a[505][505];
while(cin>>n)
{
for(i=0; i<n; i++)
{
a[0][i]=0;
a[i][0]=0;
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
cin>>a[i][j];
}
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
a[i][j]=max(a[i-1][j],a[i][j-1])+a[i][j];
}
}
cout<<a[n][n]<<endl;
}
return 0;
}
2.编辑距离问题
给定两个字符串S和T,对于T我们允许三种操作:
(1) 在任意位置添加任意字符
(2) 删除存在的任意字符
(3) 修改任意字符
问最少操作多少次可以把字符串T变成S?
例如: S= “ABCF” T = “DBFG”
那么可以
把D改为A
(2) 删掉G
(3) 加入C
所以答案是3。
分析:
给定字符串S和T,可以用一种特殊字符促成两个字符串的对齐。特殊字符是“-”, 允许在S和T中任意添加这种特殊字符使得它长度相同,然后让这两个串“对齐”,最终两个串相同位置出现了不同字符,就扣1分,要使得这两个串对齐扣分尽量少。
对于例子,采取这样的对齐方式:
12345
ABCF-
DB-FG
注意:如果要对齐,两个“-”相对是没有意义的,所以要求不出现这种情况。
那么:
(1) S,T对应位置都是普通字符,相同,则不扣分。 例如位置2,4
(2) S,T对应位置都是普通字符,不同,则扣1分。 例如位置1
(3) S在该位置是特殊字符,T在该位置是普通字符,则扣1分,例如位置5
(4) S在该位置是普通字符,T在该位置是特殊字符,则扣1分,例如位置3
扣分项目对应:
(1) 不扣分,直接对应
(2) 对应把T中对应位置的字符修改
(3) 对应在T中删除该字符
(4) 对应在T中添加该字符
设f(i,j)表示S的前i位和T的前j位对齐后的最少扣分。
最后一位对齐的情况:
(1) S[i] == T[j], 这时前i – 1和j – 1位都已经对齐了,这部分肯定要最少扣分。这种情况下最少的扣分是f(i-1,j-1)
(2) S[i]≠T[j],这种情况下最少的扣分是f(i -1, j – 1) + 1
(3) S的前i位和T的前(j – 1)位已经对齐了,这部分扣分也要最少。这种情况下最少的扣分是f(i,j-1) + 1
(4) S的前(i-1)位已经和T的前j位对齐了,这部分扣分要最少。这种情况下最少的扣分是f(i,j-1) + 1
具体f(i,j)取什么值,要看哪种情况的扣分最少。
递推式:
f(i,j) = min(f(i – 1, j – 1) + same(i,j), f(i – 1,j ) + 1, f(i, j – 1) + 1)
初值:
因为对于S的前0位,我们只能在之前加入“-”,或者说把T全部删掉了。类似地,对于T地前0位,我们只能把S的字符都加进来,别无选择。
f(0, j) = j
f(i, 0) = i
输入
第1行:字符串a(a的长度 <= 1000)。
第2行:字符串b(b的长度 <= 1000)。
输出
输出a和b的编辑距离
输入示例
kitten
sitting
输出示例
3
代码:
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
char str1[1005],str2[1005];
int f[1005][1005];
int main()
{
int i,j,n,m,z;
while(cin>>str1>>str2)
{
n=strlen(str1);
m=strlen(str2); //如:str1=kitten,str2=sitting,将str2转换为str1
for(i=0; i<=m; i++) //则:m行n列: k i t t e n (n列)
{ // 0 1 2 3 4 5 6
f[i][0]=i; // s 1 1 2 3 4 5 6
} // i 2 2 1 2 3 4 5
for(i=0; i<=n; i++) // t 3 3 2 1 2 3 4
{ // t 4 4 3 2 1 2 3
f[0][i]=i; // i 5 5 4 3 2 2 3
} // n 6 6 5 4 3 3 2
for(i=1; i<=m; i++) // g 7 7 6 5 4 4 3
{ // (m行)
for(j=1; j<=n; j++)
{
if(str1[i-1]==str2[j-1])
{
z=f[i-1][j-1];
}
else
{
z=f[i-1][j-1]+1;
}
f[i][j]=min(min(f[i-1][j]+1,f[i][j-1]+1),z);
}
}
cout<<f[m][n]<<endl;
}
return 0;
}
3.最长单增子序列(LIS)
(LIS Longest Increasing Subsequence)给定一个数列,从中删掉任意若干项剩余的序列叫做它的一个子序列,求它的最长的子序列,满足子序列中的元素是单调递增的。
例如给定序列{1,6,3,5,4},答案是3,因为{1,3,4}和{1,3,5}就是长度最长的两个单增子序列。
分析:
(1)如果a[i]大于序列最后一位元素,则将a[i]加入序列
(2)如果a[i]小于序列最后一位元素,则要找到小于a[i]的最大那一项,把它接到那个序列的后面
时间复杂度:
有单调性的存在,可以利用二分查找算法来找小于a[i]的最大那一项,所以时间复杂度是O(logm),因为m<=n,可以认为每次找到x的时间复杂度是O(logn),那么对于每个a[i]都如此做的时间复杂度就是O(nlogn)。
输入
第1行:1个数N,N为序列的长度(2 <= N <= 50000)
第2 - N + 1行:每行1个数,对应序列的元素(-10^9 <= S[i] <= 10^9)
输出
输出最长递增子序列的长度。
输入示例
8
5
1
6
8
2
4
5
10
输出示例
5
代码:
#include<cstdio>
#include<algorithm>
using namespace std;
int a[50005];
int main()
{
int id,n,x,k;
scanf("%d",&n);
k=0;
scanf("%d",&a[0]);
for(int i=1; i<n; i++)
{
scanf("%d",&x);
if(x>a[k])
{
k++;
a[k]=x;
}
else
{
id=lower_bound(a,a+k,x)-a;//找到序列中小于x的最大的一项
if(a[id]!=x)
a[id]=x;
}
}
printf("%d\n",k+1);
return 0;
}
4.最长公共子序列问题(LCS)
A和B的公共子序列中长度最长的(包含元素最多的)叫做A和B的公共子序列。
例如序列1,3,5,4,2,6,8,7和序列1,4,8,6,7,5,它们的最长公共子序列是:1,4,8,7或1,4,6,7
最长公共子序列的长度是4(最长公共子序列不唯一)。
分析:
用Ax表示序列A的连续前x项构成的子序列,即Ax= a1,a2,……ax, By= b1,b2,……by, 用LCS(x, y)表示它们的最长公共子序列长度。
令x表示子序列考虑最后一项
(1) Ax = By,那么它们L(Ax, By)的最后一项一定是这个元素,令t = Ax = By
LCS(Ax, By) = LCS(x - 1, y - 1) + 1
(2) Ax ≠ By
仍然设t = L(Ax, By), 或者L(Ax, By)是空序列(这时t是未定义值不等于任何值)。
则t ≠ Ax和t ≠ By至少有一个成立,因为t不能同时等于两个不同的值!
(2.1) 如果t ≠ Ax,则有 LCS(x,y) = LCS(x – 1, y)
(2.2) 如果t ≠ By,则有LCS(x,y) = LCS(x, y – 1)
可是事先并不知道t,由定义,取最大的一个,因此这种情况下,有
LCS(x,y) = max(LCS(x – 1, y) , LCS(x, y – 1))。
结论:
LCS(x,y) =
(1) LCS(x - 1,y - 1) + 1 如果Ax = By
(2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By
初值:
显然,一个空序列和任何序列的最长公共子序列都是空序列,所以:
LCS(x,y) =
(1) 0 如果x = 0或者y = 0
(2) LCS(x - 1,y - 1) + 1 如果Ax = By
(3) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By
复杂度:
时间复杂度时O(n * m),空间也是O(n * m)
输入
第1行:字符串A
第2行:字符串B
(A,B的长度 <= 1000)
输出
输出最长的子序列,如果有多个,随意输出1个。
输入示例
abcicba
abdkscab
输出示例
abca
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int arr[1005][1005];
char str3[1005];
int main()
{
int i,j;
string str1,str2;
while(cin>>str1>>str2)
{
int x_len=str1.length();
int y_len=str2.length();
memset(arr,0,sizeof(arr));
for(i=1; i<=x_len; i++)
{
for(j=1; j<=y_len; j++)
{
if(str1[i-1]==str2[j-1])
{
arr[i][j]=arr[i-1][j-1]+1;
}
else
{
if(arr[i][j-1]>=arr[i-1][j])
{
arr[i][j]=arr[i][j-1];
}
else
{
arr[i][j]=arr[i-1][j];
}
}
}
}
int k=0;
for(i = x_len, j = y_len; i >= 1 && j >= 1;)
{
if(str1[i - 1] == str2[j - 1])
{
str3[k++]=str1[i-1];
i--;
j--;
}
else
{
if(arr[i][j -1] > arr[i - 1][j])
{
j--;
}
else
{
i--;
}
}
}
for(i=k-1; i>=0; i--)
{
cout<<str3[i];
}
cout<<endl;
}
return 0;
}
5.最大子序列和
给出一个整数数组a(正负数都有),如何找出一个连续子数组(可以一个都不取,那么结果为0),使得其中的和最大?
例如:-2,11,-4,13,-5,-2,和最大的子段为:11,-4,13。和为20。
分析:
如果要选择a[j],那么“之前的和”一定是最大的并且是正的。不然要么把“之前的和”换成更优,要么直接从a[j]开始。
记录dp[i]表示以a[i]结尾的全部子段中最大的和。如果取a[i – 1]则一定是取以a[i – 1]结尾的子段和中最大的一个,所以是dp[i – 1]。如果不取dp[i – 1],就只取a[i]一个。所以有dp[i] = max(dp[i – 1] + a[i], a[i]) ,和dp[i] = max(dp[i – 1] , 0) + a[i]是一样的,意思是说之前能取到的最大和是正的就要,否则就不要!
初值:
dp[1] = a[1],因为前面没的选了。
空间优化:
dp[i] = max(dp[i - 1], 0) + a[i],只和dp[i – 1]有关,所以在输入序列是直接以a[i-1]替代dp[i-1]做判断。
复杂度:
时间复杂度是O(n),空间复杂度是O(1)
输入
第1行:整数序列的长度N(2 <= N <= 50000)
第2 - N + 1行:N个整数(-10^9 <= A[i] <= 10^9)
输出
输出最大子段和。
输入示例
6
-2
11
-4
13
-5
-2
输出示例
最大子序列和为:20
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long long a[50005],b[50005];
int main()
{
int i,n;
long long Max;
while(cin>>n)
{
cin>>a[0];
Max=0;
int substart=0; //求序列开始与结束点
int start=0;
int end=0;
for(i=1; i<n; i++)
{
cin>>a[i];
if(a[i-1]>0)
{
a[i]=a[i-1]+a[i];
}
else
{
substart=i;
}
if(Max<a[i])
{
Max=a[i];
start=substart;
end=i;
}
}
cout<<"最大子序列和为:"<<Max<<endl;
//cout<<"最大子序列为:a["<<start<<"]-a["<<end<<"]"<<endl;
}
return 0;
}
6.最大子矩阵和
二维的最大子段和问题,我们看看能不能把这个问题转化为一维的问题。
分析:
最后子矩阵一定是在某两行之间的。假设认为子矩阵在第i行和第j列之间,枚举所有1<=i<=j<=M,表示最终子矩阵选取的行范围。
我们把每一列第i行到第j行之间的和求出来,形成一个数组c,于是一个第i行到第j行之间的最大子矩阵和对应于这个和数组c的最大子段和。
输入
第1行:M和N,中间用空格隔开(2 <= M,N <= 500)。
第2 - N + 1行:矩阵中的元素,每行M个数,中间用空格隔开。(-10^9 <= M[i] <= 10^9)
输出
输出和的最大值。如果所有数都是负数,就输出0。
输入示例
3 3
-1 3 -1
2 -1 3
-3 1 2
输出示例
7
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[510][510];
int maxsub(int n,int a[])
{
int i,sum=0,b=0;
for(i=1; i<=n; i++)
{
if(b>0)b+=a[i];
else b=a[i];
if(b>sum)sum=b;
}
return sum;
}
int main()
{
int b[510];
int m,n,i,k,j,sum,maxsum;
while(~scanf("%d%d",&m,&n))
{
for(i=1; i<=m; i++)
{
for(j=1; j<=n; j++)
{
scanf("%d",&dp[i][j]);
}
}
maxsum=0;
for(i=1; i<=m; i++) //这部分循环很精华,求了所有方块的值
{
memset(b,0,sizeof(b));
for(j=i; j<=m; j++)
{
for(k=1; k<=n; k++)
{
b[k]+=dp[j][k]; //b[k]=b[k]+dp,把之前行的值做了累加
}
sum=maxsub(n,b); //求b的最大字段和
if(sum>maxsum)maxsum=sum; //更新整体最大字段和
}
}
printf("%d\n",maxsum);
}
return 0;
}
/*
例如:
-1 3 -1
2 -1 3
-3 1 2
m=3,n=3
遍历:
1、i=1:
(1)j=1: b数组记录 -1 3 -1
(2)j=2: b数组记录 [-1 [3 [-1
2] -1] 3]
(3)j=3: b数组记录 [-1 [3 [-1
2 -1 3
-3] 1] 2]
2、i=2:
(1)j=2: 2 -1 3
(2)j=3: [2 [-1 [3
-3] 1] 2]
3、i=3:
(1)j=3: -3 1 2
*/