最长公共子序列复杂度

最长公共子序列（LCS）问题是指：给定两个序列，找出它们最长的公共子序列。其时间复杂度为 $O(mn)$，其中 $m$ 和 $n$ 分别是两个序列的长度。LCS 问题可以用动态规划算法来解决，具体实现时需要用到一个二维数组来记录中间结果。对于序列 $A$ 和 $B$，令 $C[i][j]$ 表示 $A[1...i]$ 和 $B[1...j]$ 的最长公共子序列长度，则有以下递推式：

$$
C[i][j] =
\begin{cases}
0, & \text{if } i = 0 \text{ or } j = 0 \\
C[i-1] + 1, & \text{if } i > 0 \text{ and } j > 0 \text{ and } A[i] = B[j] \\
\max(C[i][j-1], C[i-1][j]), & \text{if } i > 0 \text{ and } j > 0 \text{ and } A[i] \neq B[j]
\end{cases}
$$

最终的 LCS 长度即为 $C[m][n]$。