题解 | 最长公共子序列(一)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;
//公共子序列的经验就是用f[i][j]代表公共子序列在数组a中从前i个元素选，在数组b中从前j个元素中选
//由于是求最值所以重复没关系
//f[i][j]可以分为f[i-1][j-1],f[i-1][j],f[i][j-1],f[i-1][j-1]+1,最后这种就是a中的第i号元素和b中的第j号元素相等，所以最后要加上1
//还要注意一代f[i-1][j]和f[i][j-1]都是包含了方案f[i-1][j-1]的，但是是求最值，所以有一些重复也无所谓，可以不用考虑f[i-1][j-1]这种情况

const int N = 1010;
char s1[N], s2[N];
int f[N][N];
int main() {
	int n, m;
	cin >> n >> m;
	scanf("%s", s1 + 1);//因为会用到i-1，所以从1开始存储，避免边界条件的讨论
	scanf("%s", s2 + 1);//注意这里不能用取地址符号
	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 (s1[i] == s2[j])f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
		}
	cout << f[n][m] << endl;
	return 0;
}