最长公共子序列（LCS）

最长公共子序列（Longest Common Subsequence，简称LCS）问题是一个经典的计算机科学问题，它要求找出两个序列（比如两个字符串或两个序列）中最长的公共子序列。一个序列可以是另一个序列的子序列，如果前者可以通过删除后者中的一些（或不删除）元素后得到，且保持原有顺序不变。

LCS问题与最长公共子串（Longest CommonSubstring）问题不同，子串必须是连续的，而子序列则不需要。

以下是解决LCS问题的动态规划方法的基本步骤：

1. 初始化：创建一个二维数组 dp，其行数为第一个序列的长度加一，列数为第二个序列的长度加一。初始化 dp[i][j] 为0，表示空序列的LCS长度为0。

2. 填充数组：遍历两个序列，对于每一对 i 和 j（1 ≤ i ≤ len(seq1) 且 1 ≤ j ≤ len(seq2)），执行以下操作：

   • 如果 seq1[i-1] 等于 seq2[j-1]（即当前字符相等），则 dp[i][j] 等于 dp[i-1][j-1] 加1，表示公共子序列长度增加1。
   • 如果 seq1[i-1] 不等于 seq2[j-1]，则 dp[i][j] 等于 dp[i-1][j] 和 dp[i][j-1] 中的较大值，表示选择不包含当前 seq1 字符或不包含当前 seq2 字符的LCS长度。

3. 返回结果：最终，dp[len(seq1)][len(seq2)] 包含了两个序列的最长公共子序列的长度。

以下是LCS问题的动态规划伪代码：

function LCS(seq1, seq2)
    let dp = array of size (len(seq1) + 1) × (len(seq2) + 1), filled with 0
    for i from 1 to len(seq1)
        for j from 1 to len(seq2)
            if seq1[i-1] == seq2[j-1]
                dp[i][j] := dp[i-1][j-1] + 1
            else
                dp[i][j] := max(dp[i-1][j], dp[i][j-1])
    return dp[len(seq1)][len(seq2)]
end function

LCS问题的一个常见应用是在数据压缩中的文本比较，如diff工具。它也用于生物信息学中的基因序列比较。

LCS问题的时间复杂度是 O(m n)，其中 m 和 n 分别是两个序列的长度。空间复杂度也是 O(m n)，但可以通过只存储前一行和当前行来优化到 O(min(m, n))。