继续练习动态规划。

题目如下:

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=<x1,x2,…,xm>,则另一序列Z=<z1,z2,…,zk>是X的子序列是指存在一个严格递增的下标序列<i1,i2,…,ik>,使得对于所有j=1,2,…,k有:Xij=Zj

例如,序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。例如,若X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>,则序列<B,C,A>是X和Y的一个公共子序列,序列 <B,C,B,A>也是X和Y的一个公共子序列。而且,后者是X和Y的一个最长公共子序列.因为X和Y没有长度大于4的公共子序列。

给定两个序列X=<x1,x2,…,xm>和Y=<y1,y2….yn>.要求找出X和Y的一个最长公共子序列。

输入:

共有两行。每行为一个由大写字母构成的长度不超过1000的字符串,表示序列X和Y。

输出:

一个非负整数。表示所求得的最长公共子序列的长度。

样例输入:

1
2
ABCBDAB
BDCABA

样例输出:

1
4

核心:子问题拆分、递推式

定义:

1
2
3
4
5
6
7
8
9
MaxLen(i,j)为 
字符串1在索引i之前、字符串2在索引j之前的最大公共子序列

由此定义可知:
MaxLen(0,m) == 0 , 0 <= m <= len(字符串2)
MaxLen(n,0) == 0 , 0 <= n <= len(字符串1)
//原因:
//在索引0之前为空
//任意长度的字符串与空字符串都不可能有公共序列

拆分&递推:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//当str1[i-1] == str2[j-1]时
MaxLen[i][j] = MaxLen[i-1][j-1] + 1;
/*
为什么合理?
因为递推将从i=1,j=1开始(索引第二位),
每个位置的最大公共子序列都是从第一位开始计算的
因为str1[i-1] == str2[j-1],所以子序列长度+1,
则可以在MaxLen[i-1][j-1](注意定义)的基础上
再加一。
*/

//当str1[i-1] != str2[j-1]时
MaxLen[i][j] = max(MaxLen[i-1][j] , MaxLen[i][j-1]);
/*
为什么合理?
因为当str1[i-1] != str2[j-1]时,
可能存在如下几种情况:
1.包含str2[j]之后,最大公共子序列更长
2.包含str1[i]之后,最大公共子序列更长
3.包含二者其中之一时,最大公共子序列长度不变
因此,max(MaxLen[i-1][j] , MaxLen[i][j-1])
可以保证取到最长的子序列,还可以保证不满足时
之前取得的最大子序列不变,填入MaxLen[i][j]
*/

有了递推式,程序就会变得简单许多。

程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s1,s2;
int MaxLen[1005][1005];
int main(void){
cin >> s1 >> s2;
/*-----取得长度-----*/
int length1 = s1.length();
int length2 = s2.length();
/*-----边界初始化,详见“定义”-----*/
for(int i=0;i <= length1;i++){
MaxLen[i][0] = 0;
}
for(int i=0 ; i <= length2;i++){
MaxLen[0][i] = 0;
}
/*-----根据递推公式,双重循环递推-----*/
for(int i=1;i <= length1;i++){
for(int 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]);
}
}
}
/*-----输出结果(注意MaxLen定义)-----*/
cout << MaxLen[s1.length()][s2.length()] << endl;
//Prints:4
return 0;
}

总结:

心累