求解两个字符串的最长公共⼦序列
⼀，问题描述
给定两个字符串，求解这两个字符串的最长公共⼦序列（Longest Common Sequence）。⽐如字符串1：BDCABA；字符串2：ABCBDAB 则这两个字符串的最长公共⼦序列长度为4，最长公共⼦序列是：BCBA
⼆，算法求解
这是⼀个动态规划的题⽬。对于可⽤动态规划求解的问题，⼀般有两个特征：①最优⼦结构；②重叠⼦问题
①最优⼦结构
设 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是两个序列，将 X 和 Y 的最长公共⼦序列记为LCS(X,Y)
出LCS(X,Y)就是⼀个最优化问题。因为，我们需要到X 和 Y中最长的那个公共⼦序列。⽽要X 和 Y的LCS，⾸先考虑X的最后⼀个元素和Y的最后⼀个元素。
1）如果 xn=ym，即X的最后⼀个元素与Y的最后⼀个元素相同，这说明该元素⼀定位于公共⼦序列中。因此，现在只需要：LCS(X n-
1，Y m-1)
LCS(X n-1，Y m-1)就是原问题的⼀个⼦问题。为什么叫⼦问题？因为它的规模⽐原问题⼩。（⼩⼀个元素也是⼩嘛....）
为什么是最优的⼦问题？因为我们要的是X n-1 和 Y m-1的最长公共⼦序列啊。。。最长的换句话说，就是最优的那个。（这⾥的最优就是最长的意思）
2）如果xn != ym，这下要⿇烦⼀点，因为它产⽣了两个⼦问题：LCS(X n-1，Y m) 和 LCS(X n，Y m-1)
因为序列X 和序列Y 的最后⼀个元素不相等嘛，那说明最后⼀个元素不可能是最长公共⼦序列中的元素嘛。（都不相等了，怎么公共嘛）。LCS(X n-1，Y m)表⽰：最长公共序列可以在(x1,x2,....x(n-1)) 和 (y1,y2,...yn)中。
LCS(X n，Y m-1)表⽰：最长公共序列可以在(x1,x2,....xn) 和 (y1,y2,...y(n-1))中。
求解上⾯两个⼦问题，得到的公共⼦序列谁最长，那谁就是 LCS（X,Y）。⽤数学表⽰就是：
LCS=max{LCS(X n-1，Y m)，LCS(X n，Y m-1)}
由于条件 1) 和 2) 考虑到了所有可能的情况。因此，我们成功地把原问题转化成了三个规模更⼩的⼦问题。
②重叠⼦问题
重叠⼦问题是啥？就是说原问题转化成⼦问题后，⼦问题中有相同的问题。咦？我怎么没有发现上⾯的三个⼦问题中有相同的啊OK，来看看，原问题是：LCS(X,Y)。⼦问题有❶LCS(X n-1，Y m-1) ❷LCS(X n-1，Y m) ❸LCS(X n，Y m-1)
初⼀看，这三个⼦问题是不重叠的。可本质上它们是重叠的，因为它们只重叠了⼀⼤部分。举例：
第⼆个⼦问题：LCS(X n-1，Y m) 就包含了：问题❶LCS(X n-1，Y m-1)，为什么？
因为，当X n-1和 Y m的最后⼀个元素不相同时，我们⼜需要将LCS(X n-1，Y m)进⾏分解：分解成：LCS(X n-1，Y m-1) 和 LCS(X n-2，Y m)
也就是说：在⼦问题的继续分解中，有些问题是重叠的。
由于像LCS这样的问题，它具有重叠⼦问题的性质，因此：⽤递归来求解就太不划算了。因为采⽤递归，它重复地求解了⼦问题啊。⽽且注意哦，所有⼦问题加起来的个数可是指数级的哦。。。。
中就演⽰了⼀个递归求解重叠⼦问题的⽰例。
那么问题来了，你说⽤递归求解，有指数级个⼦问题，故时间复杂度是指数级。这指数级个⼦问题，难道⽤了动态规划，就变成多项式时间了？？
呵呵哒。。。。
关键是采⽤动态规划时，并不需要去⼀⼀计算那些重叠了的⼦问题。或者说：⽤了动态规划之后，有些⼦问题是通过 “查表“ 直接得到的，⽽不是重新⼜计算⼀遍得到的。废话少说：举个例⼦吧！⽐如求Fib数列。关于Fib数列，
求fib(5)，分解成了两个⼦问题：fib(4) 和 fib(3)，求解fib(4) 和 fib(3)时，⼜分解了⼀系列的⼩问题....
从图中可以看出：根的左右⼦树：fib(4) 和 fib(3)下，是有很多重叠的⽐如，对于 fib(2)，它就⼀共出现了三次。如果⽤递归来求
解，fib(2)就会被计算三次，⽽⽤DP(Dynamic Programming)动态规划，则fib(2)只会计算⼀次，其他两次则是通过”查表“直接求得。⽽且，更关键的是：查求得该问题的解之后，就不需要再继续去分解该问题了。⽽对于递归，是不断地将问题分解，直到分解为基准问题(fib(1)或者 fib(0))
说了这么多，还是要写下最长公共⼦序列的递归式才完整。借⽤⽹友的⼀张图吧：）
c[i,j]表⽰：(i) 和 (j) 的最长公共⼦序列的长度。（是长度哦，就是⼀个整数嘛）。公式的具体解释可参考《算法导论》动态规划章节
这张DP表很是重要，从中我们可以窥见最长公共⼦序列的来源，同时可以根据这张表打印出最长公共⼦序列的构成路径
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4using namespace std;
5const int N = 1000;
6char a[N],b[N];
7int dp[N][N];
8int main()
9 {
10int lena,lenb,i,j;
11while(scanf("%s%s",a,b)!=EOF)
12 {
13 memset(dp,0,sizeof(dp));
14 lena=strlen(a);
15 lenb=strlen(b);
16for(i=1;i<=lena;i++)
17 {
18for(j=1;j<=lenb;j++)
19 {
20if(a[i-1]==b[j-1])
21 {
22 dp[i][j]=dp[i-1][j-1]+1;
23 }
24else
25 {
26 dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
27 }
28 }
29 }
30 printf("%d\n",dp[lena][lenb]);
31 }
32return0;
33 }
最长公共⼦序列打印路径的模板
递归法：
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4using namespace std;
5const int N = 1010;
6char a[N],b[N];
7int dp[N][N];
8int flag[N][N];
9void Print(int i,int j)
10 {
11if(i==0||j==0)///递归终⽌条件
12 {
13return ;
14 }
15if(!flag[i][j])
16 {
17 Print(i-1,j-1);
18 printf("%c",a[i-1]);
19 }
20else if(flag[i][j]==1)
21 {
22 Print(i-1,j);
23 }
24else if(flag[i][j]=-1)
25 {
26 Print(i,j-1);
27 }
28 }
29int main()
30 {
31int lena,lenb,i,j;
32while(scanf("%s%s",a,b)!=EOF)
33 {
34 memset(dp,0,sizeof(dp));
35 memset(flag,0,sizeof(flag));
36 lena=strlen(a);
37 lenb=strlen(b);
38for(i=1;i<=lena;i++)
39 {
40for(j=1;j<=lenb;j++)
41 {
42if(a[i-1]==b[j-1])
43 {
44 dp[i][j]=dp[i-1][j-1]+1;
45 flag[i][j]=0;///来⾃于左上⽅
46 }
47else
48 {
49if(dp[i-1][j]>dp[i][j-1])
50 {
51 dp[i][j]=dp[i-1][j];
52 flag[i][j]=1;///来⾃于左⽅
53 }
54else
55 {
56 dp[i][j]=dp[i][j-1];
57 flag[i][j]=-1;///来⾃于上⽅
58 }
59 }
60 }
61 }
62 Print(lena,lenb);
63 }
64return0;
65 }
View Code
⾮递归，在这⾥因为是逆序的回溯，所以我使⽤了栈来存储路径
1 #include<stdio.h>
2 #include<string.h>
字符串长度0到593 #include<stack>
4 #include<algorithm>
5using namespace std;
6#define N 1010
7int dp[N][N];
8char c;
9int main()
10 {
11char a[N];
12char b[N];
13 scanf("%s%s",a,b);
14int la=strlen(a);
15int lb=strlen(b);
16 memset(dp,0,sizeof(dp));
17for(int i=1; i<=la; i++)
18 {
19for(int j=1; j<=lb; j++)
20 {
21if(a[i-1]==b[j-1])
22 dp[i][j]=dp[i-1][j-1]+1;
23else
24 dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
25 }
26 }
27int i=la,j=lb;
28 stack<char>s;
29while(dp[i][j])
30 {
31if(dp[i][j]==dp[i-1][j])///来⾃于左⽅向
32 {
33 i--;
34 }
35else if(dp[i][j]==dp[i][j-1])///来⾃于上⽅向
36 {
37 j--;
38 }
39else if(dp[i][j]>dp[i-1][j-1])///来⾃于左上⽅向
40 {
41 i--;
42 j--;
43 s.push(a[i]);
44 }
45 }
46while(!s.empty())
47 {
48 p();
49 printf("%c",c);
50 s.pop();
51 }
52return0;
53 }
参考资料：
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论