最長公共子序列，英文縮寫為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]);
    }