算法：最長公共子序列問題

問題背景#

給定兩個字符串 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 路徑。因為路徑信息已經在空間壓縮中丟掉了。