最长公共子序列问题

最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

ex：两个字符串s，t，求两个字符串中最长的公共子序列的长度

dp[i][j] :=s1......si和t1.....tj

由此定义,s1......si,si+1 和t1.....tj,sj+1对应的公共子序列可能为以下

1. si+1 == sj+1的公共子列末尾加上si+1
2. s1......si,和t1.....tj,sj+1的公共子列
3. 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]);
    }