最长公共子序列（LCS）

loading...

最长公共子序列（LCS）详解与 Go 语言实现

在学习完经典的背包问题后，我们再来深入探讨另一个常见的动态规划问题——最长公共子序列（Longest Common Subsequence, LCS）。这两者在思想上有许多共通之处：都涉及状态转移、子问题划分，以及通过递推或递归的方式来优化求解。但它们又解决的是完全不同类型的问题。

一、问题背景与定义

给定两个序列（字符串、数组等），最长公共子序列是指在保持各自元素相对顺序不变的前提下，两个序列共同拥有的最长子序列。

注意：

  • 子序列（subsequence）不同于子串（substring），它不要求在原序列中连续。
  • LCS 的长度可以帮助衡量两个序列的相似度，因此广泛用于文件比对、DNA 序列分析、版本控制系统 diff、文本相似度计算等场景。

示例

1
2
3
4
序列 A: ABCBDAB
序列 B: BDCAB

最长公共子序列可能是：BCAB（长度 4）

二、与背包问题的联系

在0-1 背包问题中，我们通常用一个二维数组 dp[i][w] 表示“考虑前 i 个物品，在容量为 w 的背包下能获得的最大价值”。

在 LCS 中，我们也会构造一个二维数组 dp[i][j] 表示：

在 A 的前 i 个字符和 B 的前 j 个字符中，最长公共子序列的长度。

二者的共同点是：

  • 都是 二维动态规划；
  • 都有递推关系；
  • 状态转移依赖于“较小规模问题”的结果。

三、状态转移方程

  1. 如果 A[i-1] == B[j-1]：

    1
    dp[i][j] = dp[i-1][j-1] + 1

    解释：如果当前字符相同，那么它一定属于公共子序列的一部分，所以在去掉这两个字符的情况下，结果加 1。

  2. 如果 A[i-1] != B[j-1]：

    1
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    解释：如果字符不同，那么 LCS 要么来自 A[0..i-2] 与 B[0..j-1]，要么来自 A[0..i-1] 与 B[0..j-2]，取最大值即可。

边界条件

  • 当 i == 0 或 j == 0 时，dp[i][j] = 0（空串与任何字符串的 LCS 长度为 0）。

四、Go 语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package main

import (
    "fmt"
)

// LCS 返回最长公共子序列的长度
func LCS(a, b string) int {
    m, n := len(a), len(b)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if a[i-1] == b[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                if dp[i-1][j] > dp[i][j-1] {
                    dp[i][j] = dp[i-1][j]
                } else {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }
    return dp[m][n]
}

func main() {
    a := "ABCBDAB"
    b := "BDCAB"
    fmt.Printf("LCS(\"%s\", \"%s\") = %d\n", a, b, LCS(a, b))
}

输出结果

1
LCS("ABCBDAB", "BDCAB") = 4

五、优化与扩展

  1. 空间优化：
    因为 dp[i][j] 只依赖于上一行和当前行，所以可以将空间从 O(m*n) 优化到 O(min(m, n))。

  2. 恢复具体序列：
    在计算过程中记录选择路径，可以反向回溯出一个实际的最长公共子序列。

  3. 多序列 LCS：
    LCS 也可以推广到三个及以上的序列，不过维度会增加，复杂度也会急剧上升。

六、总结

  • LCS 问题与背包问题的思路高度相似，都是动态规划的经典应用。
  • 它的状态转移依赖于当前字符是否相等，并在二维表中逐步填充结果。
  • 在工程实践中，LCS 是文件差异比较、版本控制系统（如 Git diff）的底层原理之一。

在掌握了 LCS 之后，你会发现很多看似完全不同的算法问题，其核心都是围绕着“如何将一个大问题分解为小问题，并利用小问题的解来构建整体解”。这正是动态规划的精髓所在。