3061: 公共子序列

解题思路:f[i][j] 表示a字符串前i字符与b字符串前j字符的最大公共子序列长度

注意事项:

参考代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e2 + 10;
int f[N][N];
string a,b;
int main()
{
	while(cin >> a >> b){
		memset(f, 0, sizeof f);
		for(int i = 1; i <= a.size(); i ++)
			for(int j = 1; j <= b.size(); 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[a.size()][b.size()] << endl;
	}
	return 0;
}