动态规划篇——最长公共子序列(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];//输出最长子序列
}

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
34
35
36
37
38