最长公共子序列

题目链接：https://www.acwing.com/problem/content/899/

题目描述

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

输入描述

第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。

输出描述

输出一个整数，表示最大长度。
1≤N,M≤1000

示例

输入

4 5
acbd
abedc

输出

3

分析

约定

记第一个字符串为a，第二个为b

状态表示

f(i,j)所代表的集合和属性如下：

• 集合：从a中前i个字母，b中前j个字母中选择出的公共子序列
• 属性：所有子序列长度的最大值

状态划分与计算

从状态表示中集合的角度切入，对于f(i,j),其集合中的公共子序列存在四种情况：

• 有a[i],b[j]，且a[i]=b[j]
• 有a[i]，无b[j]
• 无a[i]，有b[j]
• 无a[i],b[j]

我们要做的就是先求出各种情况的最大长度，再求四种情况的最大长度。
显然，有a[i],b[j]和无a[i],b[j]的情况较为简单，分别为：
f(i-1,j-1)+1
f(i-1,j-1)
另外两种才是难点，以有a[i]，无b[j]为例分析。
我们一般会想到f(i,j-1)，但请思考这个式子所代表的集合与我们要求解的情况一致吗？
肯定不一致，f(i,j-1)是一个包含了该情况的更大的集合，但恰恰该情况的最大值已经被f(i,j-1)所考虑了。即我们虽然不能说f(i,j-1)就是该情况的最大值，但通过它就能将该情况的最大值考虑进去。
另一种情况同理，通过f(i-1,j)间接考虑。

状态转移方程

由上一步的分析，我们得到状态转移方程如下：

• f(i,j)=max(f(i-1,j-1),f(i,j-1),f(i-1,j))   a[i]!=b[j]
• f(i,j)=max(f(i-1,j-1),f(i,j-1),f(i-1,j),f(i-1,j-1)+1)   a[i]=b[j]

在此，再对我们的状态计算的方法进行说明，我们的目的是求出四种情况中的最大值，但我们并不是通过先分别求出最大值再比较得到的，而是间接的实现，状态转移方程中的各个比较项是存在交叉的，但它们的并集涵盖了f(i,j)集合中的所有元素，从而实现的求解，这是集合思想的巧妙运用。
另外，虽然状态转移方程中有f(i-1,j-1)，但该值其实已经被f(i,j-1)或f(i-1,j)所考虑，因此实际编程时我们通常不写它。

AC代码

---

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int N = 1001;

int n, m;
string a, b;
int f[N][N];

int main()
{
	cin >> n >> m;
	cin >> a >> b;
	for (int i = 1; i <= a.length(); i++)
	{
		for (int j = 1; j <= b.length(); j++)
		{
			f[i][j] = max(f[i - 1][j], f[i][j - 1]);
			if (a[i-1] == b[j-1])
				f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
		}
	}
	cout << f[n][m] << endl;
	return 0;
}