这里，为了更方便地解释，我以洛谷上的一道典型题目为例，为大家讲解处理最长公共子序列问题的几种常见方法。这道题目中规定了两个子序列的长度相等，如果遇到不等的情况，也只需要对长度稍作修改即可，算法思想不变。

题目描述

给出 1，2，…… ，n 的两个排列 A 和 B ，求它们的最长公共子序列。

输入格式

第一行是一个数 n。

接下来两行，每行为 n 个数，为自然数 1，2，…… ，n 的一个排列。

输出格式

一个数，即最长公共子序列的长度。

样例输入 
5 
3 2 1 4 5
1 2 3 4 5

样例输出 
3

提示

- 对于 50% 的数据， n <= 10^3；
- 对于 100% 的数据， n <= 10^5。

方法1：常规动态规划

要解决这道题目，必然要使用动态规划。既然要用到动态规划，就要知道状态转移方程。我们令L[i][j] 表示序列 A 和序列 B 的最长公共子序列的长度，则状态转移方程如下：

若a[i]b[j]， 则 L[i][j]L[i-1][j-1] +1

若a[i]b[j]， 则 L[i][j]max (L[i][j-1]，L[i-1][j]）

以表格的形式表示整个过程如下：（这里以 3 2 1 4 5 和1 2 3 4 5为例）

i\j	0	3	2	1	4	5
0	0	0	0	0	0	0
1	0	0	0	1	1	1
2	0	0	1	1	1	1
3	0	1	1	1	1	1
4	0	1	1	1	2	2
5	0	1	1	1	2	3

填表的过程就相当于解题的过程（第0行、第0列初始值都为0），我们以第0行为参照，先从左到右填满第1行；再以第1行为参照，从左到右填满第2行；以此类推，当表格填完后，答案就出来了（即为L[n][n]）。

代码如下：

# include <iostream>

using namespace std;

const int maxn = 1e3 + 10;
int n;
int A[maxn];
int B[maxn];
int L[maxn][maxn];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> B[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			//对应状态转移方程
			if (A[i] == B[j]) {
				L[i][j] = L[i - 1][j - 1] + 1;
			}
			else {
				L[i][j] = max(L[i - 1][j], L[i][j - 1]);
			}
		}
	}
	cout << L[n][n] << endl;
	return 0;
}

这种方法是最基本的方法。容易看出它的时间复杂度是O(n^2)；但这种方法有一个缺点，就是对空间的要求非常高，因为我们创建了一个二维数组 L，所以空间复杂度为O(n^2) ，如果 n 的值比较大，那么我们就无法创建 L数组了。因此，下面又给出了一种节省空间的办法。

方法2：改进常规动态规划

我们的算法思想还和原来基本一致，只不过，我们要把二维数组 L 变成一个一维数组。实现的思想如下：在填表的过程中，我们可以发现，当我们在填某一行时，我们其实只需要用到上一行的数组作为参照，表格中其他的部分并没有用。所以，我们想到，可以只创建一个一维数组 L ，保存需要用作参照的上一行数据；用一个变量 ans 保存计算得到的需要填入表格的新值；在填写当前一行数据的同时，更新数组 L已经遍历过的部分（后面不再用到）为当前行的数据（相当于把当前行的数据逐步填入 L）；这样，在填写下一行数据时，L也已经更新为新的参照行。最后得到的 ans 就相当于原表格最右下角的位置，即为最终答案。

改进后的代码如下：

# include <iostream>

using namespace std;

const int maxn = 1e5 + 10;
int n;
int A[maxn];
int B[maxn];
int L[maxn];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> B[i];
	}
	int ans = 0, t;
	for (int i = 1; i <= n; i++) {
		ans = 0;
		for (int j = 1; j <= n; j++) {
			t = ans;  //提前记录上一个ans的值
			if (A[i] == B[j]) {
				ans = L[j - 1] + 1;
			}
			else {
				ans = max(ans, L[j]);
			}
			//对已经遍历过的地方将L更新为下一行的值
			L[j - 1] = t;  
		}
		L[n] = ans;  
	}
	//运行到最后，ans便是原二维数组最右下角的结果
	cout << ans << endl;
	return 0;
}

方法2和方法1算法思想基本一致，时间复杂度也都是 O(n^2)，但方法2的空间复杂度只有 O(n)，显然是方法2更胜一筹（当然，某一问题所需要的空间不大时，我们还是优先选择方法1，因为方法1写起来更简便）。

但上述两种做法，时间复杂度都是 O(n^2)。遇到某些对时间限制比较高的情况，就不适用了，所以，我们又提出了下面一种方法。

方法3：巧用另一种动态规划

上面解决最长公共子序列问题的算法可简称为LCS。我们还有另一种巧妙的方法来解决这类问题，就是将LCS转化为LIS。什么是LIS呢？LIS是解决最长递增（或不下降）子序列的算法。LIS算法的核心思想也是动态规划。我们先来讲讲转化的过程：

能够转化的前提是序列A和序列B的数据范围必须相同

我们仍以 3 2 1 4 5 和 1 2 3 4 5 为例

A: 3 2 1 4 5

B: 1 2 3 4 5

我们把A中的数据按顺序变成1、2、3、4、5（变成递增顺序），即3 -> 1，2 -> 2，1 -> 3，4 -> 4，5 -> 5；然后B按照A的转化规则进行转化，于是变成：

A: 1 2 3 4 5
B: 3 2 1 4 5

这样标号之后，序列的长度显然不会改变。但是出现了一个性质：两个序列的子序列，一定是A的子序列。而A本身就是递增的，因此这个子序列是递增的。换句话说，只要这个子序列在B中递增，它就是A的子序列。于是，问题就转化成了求B中的最长递增子序列。

你可能觉得这样的转化多此一举，但请注意，解决最长递增子序列类问题，时间复杂度最低可以达到 O(nlogn)；也就是说，用这种方法，我们可以将求解最长公共子序列问题的时间复杂度降为O(nlogn)，这样在处理相关问题时就可以避免时间超限的情况。

但新的问题又来了，怎么在O(nlogn)时间复杂度内求解最长递增子序列问题？这里，我参考了别人给出的一个解释：

我们以数列 5 2 3 1 4 为例

首先，把 5 加入答案序列中，然后遍历到 2，发现 2<5 , 于是，我们用2替换5；然后加3，发现3>2，所以直接把3加到答案序列中，这时候就是 [2,3] ;然后遍历到1，我们发现1<3，于是我们找到一个最小的但是比1大的数字2，然后把1替换2，为什么这么做不会影响结果呢？你可以这么想，我们当前已经求出了一个当前最优的序列，如果我们用1替换2，然后后面来一个数字替换了3，那么我们就可以得到一个更优的序列，而如果没有数字替换3，那么这个1替换2也就是没有贡献的，不会影响我们结果的最优性。另外，解题时可以直接使用STL的lower_bound函数来找到一个最小的但是大于某个数字的数。

代码如下：

# include <iostream>
# include <vector>
# include <map>

using namespace std;

const int maxn = 1e5 + 10;
int n;
map<int, int>m;
int B[maxn];

int main()
{
	cin >> n;
	int a;
	for (int i = 1; i <= n; i++) {
		cin >> a;
		m[a] = i;
	}
	int b;
	for (int i = 1; i <= n; i++) {
		cin >> b;
		//按照A的转化规则，转化B
		B[i] = m[b];
	}
	//序列C用于保存当前的最优解
	vector<int>C;
	C.push_back(0);
	int len = 0; //保存最终结果
	for (int i = 1; i <= n; i++) {
		if (B[i] > C[len]) {
			C.push_back(B[i]);
			len++;
		}
		else {
			C[lower_bound(C.begin(), C.end(), B[i]) - C.begin()] = B[i];
		}
	}
	cout << len << endl;
	return 0;
}

用这种方法时间复杂度就降为O(nlogn)了。我上面给出的那一道题，也只有采用这种方法才不会时间超限。而前两种只能得一半的分。

总结：

这里，我给出了解决最长公共子序列的三种方法，大家可以根据实际问题，各取所需。以上便是我的看法，很高兴与大家分享。