算法：最长公共子序列问题

问题背景#

给定两个字符串 A 和 B，找出它们的最长公共子序列。

子序列：可以不连续，但保持原顺序
公共子序列：同时是 A 和 B 的子序列

示例：

A = "ABCBDAB"
B = "BDCAB"

LCS = "BDAB" 或 "BCAB"（都长度为4）

应用#

文件 / 代码差异比较（如 diff 工具）
基因序列比对（DNA / 蛋白质）
拼写纠错、版本控制合并
编辑距离、语义相似性计算

动态规划求解#

思路：定义 $dp[i][j]$ 表示 $A[0..i-1]$ 与 $B[0..j-1]$ 的最长公共子序列长度。

伪码（包含状态转移方程）：

def LCS_length(A, B):
    n, m = len(A), len(B)
    dp = [[0] * (m+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, m+1):
            if A[i-1] == B[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[n][m]

时间复杂度： $O(m\times n)$
空间复杂度： $O(m\times n)$

回溯与序列恢复#

  # ...

  # 回溯恢复路径
  i, j = n, m
  lcs = []
  while i > 0 and j > 0:
      if A[i-1] == B[j-1]:
          lcs.append(A[i-1])
          i -= 1
          j -= 1
      elif dp[i-1][j] >= dp[i][j-1]:
          i -= 1
      else:
          j -= 1

  return ''.join(reversed(lcs))

滚动数组优化空间复杂度#

在二维 DP 表中，如果某一行的值只依赖于 “前一行”，那么我们不需要保留整个二维表 —— 只需保存当前行和上一行即可，循环滚动使用。

原始状态转移：

if A[i-1] == B[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

每个 dp [i][j] 只依赖于 i-1 行的数据，所以可以用滚动数组优化空间

滚动数组实现方式
只保留 2 行

prev = [0] * (m + 1)  # 前一行
curr = [0] * (m + 1)  # 当前行

每处理完一行 i，就交换 prev 和 curr

def LCS_length(A, B):
    n, m = len(A), len(B)
    prev = [0] * (m + 1)
    curr = [0] * (m + 1)

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if A[i - 1] == B[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev, curr = curr, prev  # 交换两行

    return prev[m]  # 注意最终结果在 prev（因为最后一轮交换了）

时间复杂度仍然是 $O(m\times n)$
空间复杂度降为 $O(\min\{m, n\})$

但注意：不能根据滚动数组恢复 LCS 路径。因为路径信息已经在空间压缩中丢掉了。