最长公共子序列--LCS（dp入门）_lcs dp

Longest common subsequence（缩写：LCS）最长公共子序列， dp经典入门题。有时会和我上一篇文章讲的最长单调子序列问题（LIS）结合起来一起考。这里单独讲LCS，比LIS复杂一点点。但这两种题型都可以套模板。

定义：
什么是最长公共子序列呢?好比一个数列S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。

举个例子，如：有两条随机序列，如 1 3 4 5 5 ，and 2 4 5 5 7 6，则它们的最长公共子序列便是：4 5 5。
1

例题一：最长公共子序列
题目描述
一个给定的子序列是在该序列中删去若干元素后得到的序列。例如，序列z=<B,C,D,B> 是序列X=<A,B,C,B,D,A,B>的子序列；
给定两个序列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的一个公共子序列；
编程求出给定的两个序列中，最长公共子序列的长度。

输入
共两行，各一个字符串，第一个字符串表示第一个序列，第二个字符串表示第二个序列，两个字符串长度均小于1000。

输出
一个整数，即两个序列的公共子序列的长度。

样例输入
aabaaecd
abcd
样例输出
4

分析：
1、暴搜绝对超时。复杂度O（2 ^ m * 2 ^ n）。m、n为两序列的长度，指数级增长。

2、dp会怎么做呢？
（1）因为两个序列比较，所以dp数组是二维的。而序列是有顺序的，无后效性（在这里的意思是序列的前面几个数的决定不会影响后面的数 ），还不如不解释 。

（2）这类字符比较的题目，让我想起之前整理的dp入门题中最重要的金矿模型和字符串距离问题。（这里不熟悉的话，可以回顾我之前的文章 动态规划入门）
金矿模型，是让我们逆向思维，于是字符串距离问题中得出递推格式。

	for(int i=1;i<=t1;i++){
		for(int j=1;j<=t2;j++){
			if(a[i-1]==b[j-1])	dp[i][j]=dp[i-1][j-1];
			else
				dp[i][j]=min(dp[i-1][j-1]+abs(a[i-1]-b[j-1]),min(dp[i-1][j],dp[i][j-1])+k);
			
		}
	} 
	cout<<dp[t1][t2]<<endl;

1
2
3
4
5
6
7
8
9
10

这里面状态转移公式先忽略，这里的逆向思维体现在下面这个模板

for(int i=1;i<=t1;i++){
	for(int j=1;j<=t2;j++){
		dp[i][j]=关于dp[i-1][j]或dp[i][j-1]或其它的状态转移公式
	}
}
1
2
3
4
5

要求dp[i][j]（以第i个为结尾的序列A与以第j个为结尾的序列B的LCS）的话，只要知道dp[i-k][j]和dp[i][j-k]，一直递推到最开始。k为任意值，但在这两层循环中i，j可以遍历，dp[i-1][j]或dp[i][j-1]便可以达到dp[i-k][j]和dp[i][j-k]的效果。

所以这便是字符串比较或序列相关dp题的一种遍历的模板。

那么这题便不难解决。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
string a,b;
int dp[1005][1005];
int main(){
	getline(cin,a);
	getline(cin,b);
	int n=a.size();
	int m=b.size();
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i-1]==b[j-1])	dp[i][j]=dp[i-1][j-1]+1;
			else	dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 
		}
	}
	cout<<dp[n][m]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21