https://vjudge.net/problem/Aizu-ALDS1_10_C

求两个字符串的最长公共子序列

思想：如果xm=yn lcs后面加上xm(yn)
如果xm!=yn lcs为max(lcs(xm-1,yn),lcs(xm,yn-1))

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
#include<sstream>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
int dp[maxn][maxn];

int lcs(string s1, string s2) {
	memset(dp, 0, sizeof(dp));
	int l1 = s1.length();
	int l2 = s2.length();
	int ans = 0;
	s1 = ' ' + s1;
	s2 = ' ' + s2;
	for (int i = 1; i <= l1; i++) {
		for (int j = 1; j <= l2; j++) {
			if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
			ans = max(ans, dp[i][j]);
		}
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s1, s2;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s1 >> s2;
		cout << lcs(s1, s2)<<endl;
	}
	return 0;
}