动态规划算法 - 最长公共子序列 - 求解最长公共子序列

动态规划算法 - 最长公共子序列 - 求解最长公共子序列

一、引言

在计算机科学和数学领域中，经常会遇到需要比较两个序列并找出它们之间相似部分的问题。最长公共子序列（Longest Common Subsequence，LCS）问题就是这类问题中的经典代表。它在生物信息学（如基因序列比对）、版本控制系统（如比较文件的不同版本）等众多领域都有广泛的应用。本文将深入探讨如何使用动态规划算法来求解最长公共子序列问题。

二、基本概念

2.1 子序列的定义

给定一个序列 $X = [x1, x_2,…, x_m]$，另一个序列 $Z = [z_1, z_2,…, z_k]$ 是 $X$ 的子序列，当且仅当存在一个严格递增的下标序列 $[i_1, i_2,…, i_k]$，使得对于所有的 $j = 1, 2,…, k$，都有 $z_j = x{i_j}$。例如，序列 $X = [1, 3, 4, 5, 6, 7, 7, 8]$，则 $Z = [1, 4, 5, 8]$ 是 $X$ 的一个子序列。

2.2 最长公共子序列的定义

给定两个序列 $X$ 和 $Y$，它们的公共子序列是同时属于 $X$ 和 $Y$ 的子序列。最长公共子序列就是所有公共子序列中长度最长的那个。例如，对于序列 $X = [1, 3, 4, 5, 6, 7, 7, 8]$ 和 $Y = [3, 5, 7, 4, 8, 6, 7, 8, 2]$，它们的一个最长公共子序列是 $[3, 5, 7, 8]$，长度为 4。

三、动态规划算法原理

动态规划算法通常用于求解具有最优子结构和重叠子问题的问题。最长公共子序列问题恰好满足这两个特性。

3.1 最优子结构

设 $X = [x_1, x_2,…, x_m]$ 和 $Y = [y_1, y_2,…, y_n]$ 是两个序列，$Z = [z_1, z_2,…, z_k]$ 是它们的最长公共子序列。

• 如果 $xm = y_n$，那么 $z_k = x_m = y_n$，且 $Z{k - 1}$ 是 $X{m - 1}$ 和 $Y{n - 1}$ 的最长公共子序列。
• 如果 $xm \neq y_n$，那么 $Z$ 要么是 $X{m - 1}$ 和 $Y$ 的最长公共子序列，要么是 $X$ 和 $Y_{n - 1}$ 的最长公共子序列。

3.2 重叠子问题

在求解最长公共子序列的过程中，会多次重复计算相同子问题的解。例如，在计算 $X{i}$ 和 $Y{j}$ 的最长公共子序列时，可能会多次用到 $X{i - 1}$ 和 $Y{j - 1}$ 的最长公共子序列。

3.3 状态转移方程

设 $c[i][j]$ 表示 $X_i$ 和 $Y_j$ 的最长公共子序列的长度，则状态转移方程为：
[
c[i][j] =
\begin{cases}
0 & \text{if } i = 0 \text{ or } j = 0 \
c[i - 1][j - 1] + 1 & \text{if } i, j > 0 \text{ and } x_i = y_j \
\max(c[i - 1][j], c[i][j - 1]) & \text{if } i, j > 0 \text{ and } x_i \neq y_j
\end{cases}
]

四、算法实现

以下是使用 Python 实现的求解最长公共子序列长度的代码：

def lcs_length(X, Y):
    m = len(X)
    n = len(Y)
    # 创建一个 (m + 1) x (n + 1) 的二维数组 c 来存储子问题的解
    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return c[m][n]
# 示例
X = [1, 3, 4, 5, 6, 7, 7, 8]
Y = [3, 5, 7, 4, 8, 6, 7, 8, 2]
print("最长公共子序列的长度为:", lcs_length(X, Y))

代码解释

1. 首先，创建一个 $(m + 1) \times (n + 1)$ 的二维数组 $c$，其中 $m$ 和 $n$ 分别是序列 $X$ 和 $Y$ 的长度。$c[i][j]$ 表示 $X_i$ 和 $Y_j$ 的最长公共子序列的长度。
2. 然后，使用两层嵌套的循环遍历 $X$ 和 $Y$ 的每个元素。根据状态转移方程更新 $c[i][j]$ 的值。
3. 最后，返回 $c[m][n]$，即 $X$ 和 $Y$ 的最长公共子序列的长度。

五、回溯求解最长公共子序列

上述代码只求解了最长公共子序列的长度，要得到具体的最长公共子序列，可以使用回溯法。以下是完整的 Python 代码：

def lcs_length(X, Y):
    m = len(X)
    n = len(Y)
    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    b = [['' for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
                b[i][j] = 'diagonal'
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
                b[i][j] = 'up'
            else:
                c[i][j] = c[i][j - 1]
                b[i][j] = 'left'
    return c, b
def print_lcs(b, X, i, j):
    if i == 0 or j == 0:
        return
    if b[i][j] == 'diagonal':
        print_lcs(b, X, i - 1, j - 1)
        print(X[i - 1], end=' ')
    elif b[i][j] == 'up':
        print_lcs(b, X, i - 1, j)
    else:
        print_lcs(b, X, i, j - 1)
# 示例
X = [1, 3, 4, 5, 6, 7, 7, 8]
Y = [3, 5, 7, 4, 8, 6, 7, 8, 2]
c, b = lcs_length(X, Y)
print("最长公共子序列为:", end=' ')
print_lcs(b, X, len(X), len(Y))

代码解释

1. 在 lcs_length 函数中，除了计算 $c[i][j]$ 外，还使用一个二维数组 $b$ 来记录每个子问题的选择。
2. 在 print_lcs 函数中，根据 $b$ 数组的值进行回溯。如果 $b[i][j]$ 为 diagonal，说明 $xi = y_j$，将该元素加入最长公共子序列中，并继续回溯 $X{i - 1}$ 和 $Y{j - 1}$；如果为 up，则回溯 $X{i - 1}$ 和 $Yj$；如果为 left，则回溯 $X_i$ 和 $Y{j - 1}$。

六、复杂度分析

• 时间复杂度：算法的时间复杂度为 $O(mn)$，其中 $m$ 和 $n$ 分别是序列 $X$ 和 $Y$ 的长度。这是因为需要填充一个 $(m + 1) \times (n + 1)$ 的二维数组，每个元素的计算时间为 $O(1)$。
• 空间复杂度：空间复杂度也为 $O(mn)$，主要用于存储二维数组 $c$ 和 $b$。

七、总结

本文详细介绍了使用动态规划算法求解最长公共子序列问题的原理、实现和复杂度分析。通过定义状态转移方程，利用最优子结构和重叠子问题的特性，我们可以高效地求解最长公共子序列的长度，并通过回溯法得到具体的最长公共子序列。动态规划算法在处理这类问题时表现出了很好的性能，在实际应用中具有重要的价值。