最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
ex：两个字符串s，t，求两个字符串中最长的公共子序列的长度
dp[i][j] :=s1......si和t1.....tj
由此定义,s1......si,si+1 和t1.....tj,sj+1对应的公共子序列可能为以下
- si+1 == sj+1的公共子列末尾加上si+1
- s1......si,和t1.....tj,sj+1的公共子列
- s1......si,si+1 和t1.....tj的公共子列
有以下递推关系成立
dp[i+1][j+1] = dp[i][j] + 1 (si+1 == tj + 1)
else = max(dp[i+1][j], dp[i][j+1]
int n, m;
char s[MAX_N][MAX_N];
int dp[MAX_N + 1][MAX_N + 1];
void solve() {
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (s[i] == t[j])
{
dp[i + 1][j + 1] = dp[i][j] + 1; }
} else {
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
}
}
printf("%d\n", dp[n][m]);
}
