基于动态规划的最长公共子序列（Longest Common Subsequence, LCS）算法详解

字数 3129 2025-12-22 21:22:42

基于动态规划的最长公共子序列（Longest Common Subsequence, LCS）算法详解

题目描述
最长公共子序列（LCS）问题是寻找两个序列（在自然语言处理中通常是两个字符串或两个词序列）中最长的、不一定连续但保持相对顺序的公共子序列。给定序列 X = [x1, x2, ..., xm] 和 Y = [y1, y2, ..., yn]，目标是找到一个最长的序列 Z，使得 Z 既是 X 的子序列，也是 Y 的子序列。该算法是计算文本相似度、DNA序列比对、文件差异比较（如diff工具）和机器翻译评价（如BLEU分数的基础组件）等任务的核心。本题目将详细讲解如何利用动态规划高效求解LCS的长度及具体序列。

解题过程循序渐进讲解

第一步：问题理解与形式化定义

核心概念澄清：
- 子序列 (Subsequence)：从原序列中删除零个或多个元素（不改变剩余元素的顺序）后得到的新序列。例如，“ace” 是 “abcde” 的子序列。
- 公共子序列 (Common Subsequence)：同时是两个给定序列的子序列。对于 “ABCBDAB” 和 “BDCAB”， “BCAB” 是一个公共子序列。
- 最长公共子序列 (LCS)：所有公共子序列中长度最长的那个。可能存在多个LCS，通常算法找到一个即可。
目标：
- 计算LCS的长度。
- （可选但常见）构造出一个具体的LCS。
关键洞察：该问题具有“最优子结构”性质——两个序列的LCS的解包含它们前缀的LCS的解。这提示我们可以使用动态规划。

第二步：定义动态规划状态

设 dp[i][j] 表示序列 X 的前 i 个字符（X[0:i]）和序列 Y 的前 j 个字符（Y[0:j]）的最长公共子序列的长度。
- i 的范围是 0 到 m（m为X的长度）。
- j 的范围是 0 到 n（n为Y的长度）。
- 特别地，dp[0][j] 表示空序列与Y的前j个字符的LCS长度，显然为0。dp[i][0] 同理。
这个二维表格 dp 就是我们存储和构建最优解（长度）的结构。

第三步：推导状态转移方程
这是算法的核心。我们需要考虑当前比较的两个字符 X[i-1] 和 Y[j-1] 是否相等。

情况一：X[i-1] == Y[j-1]
- 最后一个字符相同，那么这个字符一定在LCS中。
- 因此，X[0:i] 和 Y[0:j] 的LCS长度，等于 X[0:i-1] 和 Y[0:j-1] 的LCS长度加1。
- 转移方程： dp[i][j] = dp[i-1][j-1] + 1
情况二：X[i-1] != Y[j-1]
- 最后一个字符不同，那么它们不可能同时是LCS的最后一个字符。
- 此时，LCS有两种可能的来源：
  a. 来源于 X[0:i-1] 和 Y[0:j] 的LCS。
  b. 来源于 X[0:i] 和 Y[0:j-1] 的LCS。
- 因为我们要找最长的，所以取两者中的较大值。
- 转移方程： dp[i][j] = max(dp[i-1][j], dp[i][j-1])

第四步：确定计算顺序与初始化

初始化：根据定义，dp[0][j] = 0 (对所有 j)，dp[i][0] = 0 (对所有 i)。这代表了当一个序列为空时，公共子序列长度为0。
计算顺序：由于计算 dp[i][j] 时需要其左方 (dp[i][j-1])、上方 (dp[i-1][j])、左上方 (dp[i-1][j-1]) 的值，因此我们可以按行（i从1到m）或按列（j从1到n）递推计算。通常采用双重循环：
```
for i from 1 to m:
    for j from 1 to n:
        根据状态转移方程计算 dp[i][j]
```

第五步：计算LCS长度（示例）
以 X = “ABCBDAB”, Y = “BDCAB” 为例。

初始化一个 (m+1) x (n+1) 的表格，首行首列为0。
逐行填充：
- i=1, j=1: X[0]=’A’, Y[0]=’B’，不同。dp[1][1] = max(dp[0][1]=0, dp[1][0]=0) = 0
- i=1, j=2: ‘A’ vs ‘D’，不同。dp[1][2] = max(0, 0) = 0
- ...
- i=2, j=1: ‘B’ vs ‘B’，相同。dp[2][1] = dp[1][0] + 1 = 0 + 1 = 1
- ...
- i=4, j=3: X[3]=’B’, Y[2]=’C’，不同。dp[4][3] = max(dp[3][3]=2, dp[4][2]=2) = 2
- ... 依次计算，最终 dp[7][5] = 4，即LCS长度为4。

第六步：构造一个LCS序列
为了得到具体的LCS，我们可以在填充dp表时，额外用一个direction（或b）表记录每个dp[i][j]值的来源（‘↖’, ‘↑’, ‘←’），或者直接根据完成的dp表反向回溯。

回溯方法：从 dp[m][n] 开始。
- 如果 X[i-1] == Y[j-1]，则这个字符属于LCS。将其加入结果（从末尾向前加），然后移动到 dp[i-1][j-1] (↖)。
- 如果 X[i-1] != Y[j-1]，则比较 dp[i-1][j] (↑) 和 dp[i][j-1] (←)。
  - 如果 dp[i-1][j] >= dp[i][j-1]，移动到 dp[i-1][j] (↑)。
  - 否则，移动到 dp[i][j-1] (←)。
- 当 i 或 j 为 0 时，回溯结束。
示例回溯 (X=”ABCBDAB”, Y=”BDCAB”, dp[7][5]=4)：
- (7,5): ‘B’ == ‘B’，添加’B’，移到(6,4) ↖。 LCS片段: [‘B’]
- (6,4): ‘A’ == ‘A’，添加’A’，移到(5,3) ↖。 LCS: [‘B’, ‘A’]
- (5,3): ‘D’ != ‘C’， dp[4][3]=2 >= dp[5][2]=1, 移到(4,3) ↑。
- (4,3): ‘B’ != ‘C’， dp[3][3]=2 >= dp[4][2]=2 (相等，任选，如选上)，移到(3,3) ↑。
- (3,3): ‘C’ == ‘C’，添加’C’，移到(2,2) ↖。 LCS: [‘B’, ‘A’, ‘C’]
- (2,2): ‘B’ != ‘D’， dp[1][2]=0, dp[2][1]=1，移到(2,1) ←。
- (2,1): ‘B’ == ‘B’，添加’B’，移到(1,0) ↖。 LCS: [‘B’, ‘A’, ‘C’, ‘B’]
- i或j为0，结束。最终LCS为逆序结果： “BCAB” (或 “BDAB”，取决于回溯时相等值的选择，两者都是LCS)。

第七步：算法复杂度分析

时间复杂度： O(m * n)。需要填充一个 (m+1) x (n+1) 的表格，每个单元计算是常数时间。回溯构造序列需要 O(m + n) 时间。
空间复杂度： O(m * n)，用于存储dp表。可以通过滚动数组优化到 O(min(m, n))，但此时会丢失构造具体序列的信息（除非只需求长度）。

总结
基于动态规划的LCS算法通过定义子问题状态dp[i][j]，利用最优子结构性质建立状态转移方程，以自底向上的方式递推求解，最终高效地获得了两个序列最长公共子序列的长度和内容。它是许多自然语言处理任务中衡量序列相似性或进行对齐的基础工具。

基于动态规划的最长公共子序列（Longest Common Subsequence, LCS）算法详解题目描述最长公共子序列（LCS）问题是寻找两个序列（在自然语言处理中通常是两个字符串或两个词序列）中最长的、不一定连续但保持相对顺序的公共子序列。给定序列 X = [ x1, x2, ..., xm] 和 Y = [ y1, y2, ..., yn ]，目标是找到一个最长的序列 Z，使得 Z 既是 X 的子序列，也是 Y 的子序列。该算法是计算文本相似度、DNA序列比对、文件差异比较（如diff工具）和机器翻译评价（如BLEU分数的基础组件）等任务的核心。本题目将详细讲解如何利用动态规划高效求解LCS的长度及具体序列。解题过程循序渐进讲解第一步：问题理解与形式化定义核心概念澄清：子序列 (Subsequence) ：从原序列中删除零个或多个元素（不改变剩余元素的顺序）后得到的新序列。例如，“ace” 是 “abcde” 的子序列。公共子序列 (Common Subsequence) ：同时是两个给定序列的子序列。对于 “ABCBDAB” 和 “BDCAB”， “BCAB” 是一个公共子序列。最长公共子序列 (LCS) ：所有公共子序列中长度最长的那个。可能存在多个LCS，通常算法找到一个即可。目标：计算LCS的长度。（可选但常见）构造出一个具体的LCS。关键洞察：该问题具有“最优子结构”性质——两个序列的LCS的解包含它们前缀的LCS的解。这提示我们可以使用动态规划。第二步：定义动态规划状态设 dp[i][j] 表示序列 X 的前 i 个字符（X[ 0:i]）和序列 Y 的前 j 个字符（Y[ 0:j]）的最长公共子序列的长度。 i 的范围是 0 到 m（m为X的长度）。 j 的范围是 0 到 n（n为Y的长度）。特别地， dp[0][j] 表示空序列与Y的前j个字符的LCS长度，显然为0。 dp[i][0] 同理。这个二维表格 dp 就是我们存储和构建最优解（长度）的结构。第三步：推导状态转移方程这是算法的核心。我们需要考虑当前比较的两个字符 X[i-1] 和 Y[j-1] 是否相等。情况一： X[i-1] == Y[j-1] 最后一个字符相同，那么这个字符一定在LCS中。因此， X[0:i] 和 Y[0:j] 的LCS长度，等于 X[0:i-1] 和 Y[0:j-1] 的LCS长度加1。转移方程： dp[i][j] = dp[i-1][j-1] + 1 情况二： X[i-1] != Y[j-1] 最后一个字符不同，那么它们不可能同时是LCS的最后一个字符。此时，LCS有两种可能的来源： a. 来源于 X[0:i-1] 和 Y[0:j] 的LCS。 b. 来源于 X[0:i] 和 Y[0:j-1] 的LCS。因为我们要找最长的，所以取两者中的较大值。转移方程： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 第四步：确定计算顺序与初始化初始化：根据定义， dp[0][j] = 0 (对所有 j)， dp[i][0] = 0 (对所有 i)。这代表了当一个序列为空时，公共子序列长度为0。计算顺序：由于计算 dp[i][j] 时需要其左方 ( dp[i][j-1] )、上方 ( dp[i-1][j] )、左上方 ( dp[i-1][j-1] ) 的值，因此我们可以按行（i从1到m）或按列（j从1到n）递推计算。通常采用双重循环：第五步：计算LCS长度（示例）以 X = “ABCBDAB”, Y = “BDCAB” 为例。初始化一个 (m+1) x (n+1) 的表格，首行首列为0。逐行填充： i=1, j=1: X[ 0]=’A’, Y[ 0]=’B’，不同。 dp[1][1] = max(dp[0][1]=0, dp[1][0]=0) = 0 i=1, j=2: ‘A’ vs ‘D’，不同。 dp[1][2] = max(0, 0) = 0 ... i=2, j=1: ‘B’ vs ‘B’，相同。 dp[2][1] = dp[1][0] + 1 = 0 + 1 = 1 ... i=4, j=3: X[ 3]=’B’, Y[ 2]=’C’，不同。 dp[4][3] = max(dp[3][3]=2, dp[4][2]=2) = 2 ... 依次计算，最终 dp[7][5] = 4 ，即LCS长度为4。第六步：构造一个LCS序列为了得到具体的LCS，我们可以在填充 dp 表时，额外用一个 direction （或 b ）表记录每个 dp[i][j] 值的来源（‘↖’, ‘↑’, ‘←’），或者直接根据完成的 dp 表反向回溯。回溯方法：从 dp[m][n] 开始。如果 X[i-1] == Y[j-1] ，则这个字符属于LCS。将其加入结果（从末尾向前加），然后移动到 dp[i-1][j-1] (↖)。如果 X[i-1] != Y[j-1] ，则比较 dp[i-1][j] (↑) 和 dp[i][j-1] (←)。如果 dp[i-1][j] >= dp[i][j-1] ，移动到 dp[i-1][j] (↑)。否则，移动到 dp[i][j-1] (←)。当 i 或 j 为 0 时，回溯结束。示例回溯 (X=”ABCBDAB”, Y=”BDCAB”, dp[7][5]=4 )： (7,5): ‘B’ == ‘B’，添加’B’，移到(6,4) ↖。 LCS片段: [ ‘B’ ] (6,4): ‘A’ == ‘A’，添加’A’，移到(5,3) ↖。 LCS: [ ‘B’, ‘A’ ] (5,3): ‘D’ != ‘C’， dp[4][3]=2 >= dp[5][2]=1 , 移到(4,3) ↑。 (4,3): ‘B’ != ‘C’， dp[3][3]=2 >= dp[4][2]=2 (相等，任选，如选上)，移到(3,3) ↑。 (3,3): ‘C’ == ‘C’，添加’C’，移到(2,2) ↖。 LCS: [ ‘B’, ‘A’, ‘C’ ] (2,2): ‘B’ != ‘D’， dp[1][2]=0 , dp[2][1]=1 ，移到(2,1) ←。 (2,1): ‘B’ == ‘B’，添加’B’，移到(1,0) ↖。 LCS: [ ‘B’, ‘A’, ‘C’, ‘B’ ] i或j为0，结束。最终LCS为逆序结果： “BCAB” (或 “BDAB”，取决于回溯时相等值的选择，两者都是LCS)。第七步：算法复杂度分析时间复杂度： O(m * n)。需要填充一个 (m+1) x (n+1) 的表格，每个单元计算是常数时间。回溯构造序列需要 O(m + n) 时间。空间复杂度： O(m * n)，用于存储dp表。可以通过滚动数组优化到 O(min(m, n))，但此时会丢失构造具体序列的信息（除非只需求长度）。总结基于动态规划的LCS算法通过定义子问题状态 dp[i][j] ，利用最优子结构性质建立状态转移方程，以自底向上的方式递推求解，最终高效地获得了两个序列最长公共子序列的长度和内容。它是许多自然语言处理任务中衡量序列相似性或进行对齐的基础工具。