最长公共子序列（LCS）问题

题目描述
最长公共子序列（Longest Common Subsequence, LCS）是求解两个序列（如字符串）中最长公共子序列长度的问题。子序列不要求连续，但必须保持原始顺序。例如，字符串 "abcde" 和 "ace" 的 LCS 是 "ace"，长度为 3。该问题常用于版本控制、生物基因比对等场景。

解题思路

1. 暴力枚举不可行：若两个序列长度分别为 m 和 n，子序列数量分别为 2^m 和 2^n，比较所有组合的时间复杂度为 O(2^(m+n))，效率过低。
2. 动态规划核心思想：将问题拆解为子问题，利用二维数组 dp[i][j] 记录序列 X 的前 i 个字符与序列 Y 的前 j 个字符的 LCS 长度。通过填充 dp 表，逐步推导最终结果。
3. 状态转移方程：
   • 若 X[i-1] == Y[j-1]（当前字符匹配）：dp[i][j] = dp[i-1][j-1] + 1
   • 若字符不匹配：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4. 边界条件：当 i=0 或 j=0 时，空序列与任何序列的 LCS 长度为 0。

逐步推导示例
以 X="abcde"、Y="ace" 为例：

1. 初始化 dp 表（m+1 行 x n+1 列），首行首列置 0：

   Ø a c e
Ø  0 0 0 0
a  0
b  0
c  0
d  0
e  0

2. 按行填充 dp 表：
   • i=1, j=1: X[0]='a'=Y[0] → dp[1][1]=dp[0][0]+1=1
   • i=1, j=2: 'a'≠'c' → dp[1][2]=max(dp[0][2], dp[1][1])=max(0,1)=1
   • 依此类推，最终表如下：

   Ø a c e
Ø  0 0 0 0
a  0 1 1 1
b  0 1 1 1
c  0 1 2 2
d  0 1 2 2
e  0 1 2 3

3. 读取结果：dp[m][n]=dp[5][3]=3 即为 LCS 长度。

还原 LCS 序列
从 dp[m][n] 反向回溯：

1. 若 X[i-1]=Y[j-1]，该字符属于 LCS，向左上移动（i--, j--）。
2. 若 dp[i][j] 来自上方（dp[i-1][j]），说明当前字符不属于 LCS，向上移动（i--）。
3. 若来自左方（dp[i][j-1]），向左移动（j--）。
   示例回溯路径（X="abcde", Y="ace"）：

• (5,3): 'e'='e' → 取 'e'，移至 (4,2)
• (4,2): 'd'≠'c'，比较 dp[3][2]=2 与 dp[4][1]=1 → 向上至 (3,2)
• (3,2): 'c'='c' → 取 'c'，移至 (2,1)
• (2,1): 'b'≠'a'，向上至 (1,1)
• (1,1): 'a'='a' → 取 'a'
  得到 LCS 逆序为 "eca"，反转后为 "ace"。

复杂度分析

• 时间复杂度：O(mn)，需填充 m x n 的 dp 表。
• 空间复杂度：O(mn)，可优化至 O(min(m,n))（仅保留上一行和当前行）。

常见变体

1. 输出所有 LCS（而不仅是一个）。
2. 限制子序列连续性（转化为最长公共子串问题）。
3. 多序列 LCS（维度扩展，复杂度升高）。