动态规划篇——最长公共子序列(c++)

引言：最长公共子序列属于动态规划的基础篇，由字符串的最长公共最序列可以引出很多的问题。

最长子序列详细讲解以及练习题目

需要详细讲解教程的可以观看上面链接的文章，以下是自己做的简单的概括。

一、何为最长公共子序列

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 。 请注意: 最长公共子序列不唯一，但可以长度是惟一并且相同的。

二、如何求最长公共子序列的长度

暴力枚举法：将两个字符串的所有子串相互比较，假设A、B两个子串的长度分别为m和n，那么两个子串分别有2^m和 2 ^n个子串，就需要比较 2 ^(n+m) ，时间复杂度特别复杂。

现在对暴力枚举做进一步改进，上面可以确定的是最长公共子序列长度一定是相同的，如果忽略空子序列的话，对于A长度为1的子序列有C(n,1)个，长度为2的子序列有C(n,2)个，……长度为n的子序列有C(n,n)个。对于B也可以做类似分析，即使只对序列A和序列B长度相同的子序列做比较，那么总的比较次数高达：

C(n,1)*C(m,1)*1 + C(n,2) * C(m,2) * 2+ …+C(n,p) * C(m,p)*p

其中p = min(m, n)。

在确定暴力枚举法不可取后，不妨转换下面这种思路。

我们假设两串子串（就叫A和B吧），现在假设匹配A的x位置，B的y位置（为了方便后面就叫Ax和By），那么A的（m,x)和B的（n，y）（m,n取决于两个子串的长度）已经相互匹配成功了，那现在出现的情况只有两种：匹配成功或不成功。

1、匹配成功，即Ax=By，那么最长的公共子序列长度就是在已经匹配成功的序列长度加1，LCS(x - 1, y - 1) + 1。

2、匹配不成功，即Ax!=By，这种情况下，最长的公共子序列长度不会改变并且已经求出，现在设t为最长子序列的最后一项，则t ≠ Ax和t ≠ By至少有一个成立。

2.1、如果t ≠ Ax，那么t=By，则LCS(x,y)= LCS(x – 1, y)；

2.2、如果t ≠ By，那么t=Ax，则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) LCS(x - 1,y - 1) + 1 如果Ax ＝ By

(2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By

(3) 0 如果x = 0或者y = 0。

以上是求出了最长公共子序列的长度。

三、如何求出最长公共子序列

当LCS(x – 1, y) ＝ LCS(x, y – 1)时，其实走哪个分支都一样，虽然长度时一样的，但是可能对应不同的子序列，所以最长公共子序列并不唯一。

我们在计算长度LCS(x,y)的时候只要多记录一些信息，就可以利用这些信息恢复出一个最长公共子序列来。恢复最长公共序列就好比我们在迷宫里走路，走到每个位置的时候记录下我们时从哪个方向来的，就可以从终点回到起点一样。

例题：

输入

第1行：字符串A

第2行：字符串B

(A,B的长度 <= 1000)

输出

输出最长的子序列，如果有多个，随意输出1个。

输入示例

abcicba

abdkscab

输出示例

abca

#include<iostream>#include<algorithm>#include<string.h>char a[1001],b[1001];int lcs[1001][1001];char dp[1001];using namespace std;main(){gets(a+1);gets(b+1);int l1=strlen(a+1);int l2=strlen(b+1);for(int i=0;i<=l1;i++)for(int j=0;j<=l2;j++){ if(i==0||j==0) lcs[i][j]=0;else if(a[i]==b[j]) lcs[i][j]=lcs[i-1][j-1]+1;else lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]); }int ans=l1,bns=l2,num=0;while(ans!=0&&bns!=0)//恢复最长公共序列，相当于从一串字符串中找到A、B两串中共有的字符，这里从A串中还原最长公共字符串{if(lcs[ans][bns]!=lcs[ans-1][bns])//lcs[i][j]来自于lcs[i][j-1]或者lcs[i-1][j-1],不管来自哪个，Ax肯定包含在最长公共字符串中{dp[++num]=a[ans];//记录最长公共串ans--;//继续判断A串中前一个字符bns--;//不管By来自与哪个表达式，By已经被判断过了，现在应该继续B的前一个字符}else if(lcs[ans][bns]==lcs[ans][bns-1])//如果来自lcs[i][j-1]，那么说明By不包含在最长公共字符串中，继续遍历B的前一个字符bns--;else ans--;//说明Ax不包含在最长公共字符串中，继续遍历A的前一个字符}for(int i=lcs[l1][l2];i>0;i--)cout<<dp[i];//输出最长子序列}