线性dp，897. 最长公共子序列

897. 最长公共子序列 - AcWing题库

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

输入格式

第一行包含两个整数 N 和 M。

第二行包含一个长度为 N 的字符串，表示字符串 A。

第三行包含一个长度为 M 的字符串，表示字符串 B。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N,M≤1000

输入样例：

4 5
acbd
abedc

输出样例：

3

 解析

DP的核心思想是用集合来表示一类方案，然后从集合的维度来考虑状态之间的递推关系。

 按照这个思想，我们构造dp函数及状态转移方程：
我们可以令f[i][j]为a[i],b[j]前的最长公共子序列的长度

状态计算对应集合的划分，令最后一个同学被安排在哪一排作为划分依据，可以将f[a][b][c][d][e]划分成5个不重不漏的子集：

则状态转移方程为：

f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j])f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
 
using namespace std;
typedef long long LL;
const int N = 1e3 + 5;
int n, m;
string a, b;
int f[N][N];
 
 
int main() {
	scanf("%d%d", &n, &m);
	cin >> a;
	cin >> b;
	a.insert(0, " ");
	b.insert(0, " ");
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			f[i][j] = max(f[i - 1][j], f[i][j - 1]);
			if (a[i] == b[j])f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
		}
	}
	cout <
	return 0;
}