LCS 最大公共子序列

LCS（Longest Common Subsequence）最大公共子序列，是指两个序列中都存在的最长的子序列。举个例子，对于两个序列 A 和 B：

A：ACBDEA
B：ABCDA

它们的最大公共子序列为 ACD，长度为 3。

求解 LCS 问题通常采用动态规划（DP）的方式。具体来说，设 A、B 分别为两个序列，LCS(i, j) 表示 A[1:i] 和 B[1:j] 的最长公共子序列长度。则有如下递推式：

LCS(i, j) =
1 + LCS(i-1, j-1) if A[i] == B[j]
max(LCS(i-1, j), LCS(i, j-1)) otherwise

其中，第一种情况表示 A[i] 和 B[j] 相同，那么这个字符一定在最长公共子序列里面，所以最长公共子序列的长度要加 1，并继续考虑 A[1:i-1] 和 B[1:j-1] 的 LCS 问题。第二种情况则表示 A[i] 和 B[j] 不同，那么这个字符一定不在最长公共子序列里面，此时需要考虑 A[1:i-1] 和 B[1:j]，以及 A[1:i] 和 B[1:j-1] 的 LCS 问题，取它们的最大值即可。

最终的答案即为 LCS(m, n)，其中 m 和 n 分别为 A 和 B 的长度。这个算法的时间复杂度为 O(mn)，空间复杂度也为 O(mn)。