动态规划之最长公共子序列

动态规划之最长公共子序列

1. 概念

1. 公共子序列

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。如果序列Z既是序列X的子序列又是序列Y的子序列，则称Z是X和Y的公共子序列。

2. 最长公共子序列

设序列,则$X_m=x_1,x_2,\dots ,x_m,Y_n=y_1,y_2,\dots ,y_n,Z_k=z_1,z_2,\dots ,z_k$, 最长公共子序列分如下几种情况：

• 若$x_m=y_n$, 则$Z_{k-1}$ 是$X_{m-1}$和$Y_{n-1}$的最长公共子序列.
  如：$X_3=A,B,C;Y_2=B,C$ 则最长公共子序列 $Z_2=B,C$，则$Z_1是X_2和Y_2最长公共子序列$
• 若$x_m\ne y_n且x_m\ne z_k$, 则$Z$ 是$X_{m-1}$和$Y$的最长公共子序列.
  如：$X_4=A,B,C,H;Y_3=B,C,D$ 最长公共子序列 $Z_2=B,C$，其中$X_4\ne Y_3且X_4\ne Z_2$ 则$Z是X_3和Y_3$最长公共子序列
• 若$x_m\ne y_n且y_n\ne z_k$, 则$Z$ 是$X$和$Y_{n-1}$的最长公共子序列.
  如：$X_3=B,C,D;Y_4=A,B,C,H;$ 最长公共子序列 $Z_2=B,C$，其中$X_3\ne Y_4且Y_4\ne Z_2$ 则$Z是X_3和Y_3$最长公共子序列

在分析上述最长公共子序列的情况中，当$x_m=y_n$时，有一个子问题，即 ：找出$x_{m-1}=y_{n-1}$的最长公共子序列;当$x_m\ne y_n$时，有两个子问题:即找出$x_{m-1}和y$的最长公共子序列， 和$x和y_{n-1}$的的最长公共子序列,这两个子问题都包含了同一个子问题$x_{m-1}和y_{n-1}$。 因此，本问题满足子问题重叠性质。
进一步：
令$c[i][j]$记录$X_i和Y_j$的最长公共子序列的长度，则有:
c [ i ] [ j ] = { 0 , i = 0 ， j = 0 c [ i − 1 ] [ j − 1 ] + 1 , x i = x j max ⁡ { c [ i ] [ j − 1 ] , c [ i − 1 ] [ j ] } , x i ≠ x j c[i][j] = \begin{cases} 0, & \text i=0，j=0 \\ c[i-1][j-1] + 1, & \text x_i = x_j \\ \max\{c[i][j - 1], c[i - 1][j]\} , & \text x_i \neq x_j \end{cases} c[i][j]=⎩ ⎨ ⎧​0,c[i−1][j−1]+1,max{c[i][j−1],c[i−1][j]},​i=0，j=0xi​=xj​xi​=xj​​

2. 程序跟踪

2.1 过程跟踪

例1：
$X_4=A,C,B,D;Y_4=A,B,D,A$
过程：

• $i=1,j=1;x_1=y_1;则c[1][1]=c[0][0]+1=1$
• i = 1 , j = 2 ; x 1 ≠ y 2 ; 则 c [ 1 ] [ 2 ] = max ⁡ { c [ 1 ] [ 1 ] , c [ 0 ] [ 2 ] } = 1 i=1,j=2;x_1\neq y_2;则c[1][2]= \max\{c[1][1], c[0][2]\} = 1 i=1,j=2;x1​=y2​;则c[1][2]=max{c[1][1],c[0][2]}=1
• i = 1 , j = 3 ; x 1 ≠ y 3 ; 则 c [ 1 ] [ 3 ] = max ⁡ { c [ 1 ] [ 2 ] , c [ 0 ] [ 3 ] } = 1 i=1,j=3;x_1\neq y_3;则c[1][3]= \max\{c[1][2], c[0][3]\} = 1 i=1,j=3;x1​=y3​;则c[1][3]=max{c[1][2],c[0][3]}=1
• $i=1,j=4;x_1=y_4;则c[1][4]=c[0][3]+1=1$
• i = 2 , j = 1 ; x 2 ≠ y 1 ; 则 c [ 2 ] [ 1 ] = max ⁡ { c [ 1 ] 1 ] , c [ 2 ] [ 0 ] } = 1 i=2,j=1;x_2\neq y_1;则c[2][1]= \max\{c[1]1], c[2][0]\} = 1 i=2,j=1;x2​=y1​;则c[2][1]=max{c[1]1],c[2][0]}=1
  …依次类推

b矩阵：
0 表示没有移动。
1 表示向上移动。
2 表示向左移动。
3 表示斜左上移动。

LCS回溯：
从表格的右下角开始，检查当前位置对应的字符是否相等，若相等则左上移动；若不相等比较上面和左边两个单元格，选择较大的方向移动。继续上面过程直到c[0][0]

c矩阵：

b矩阵：

例2：
$X_4=B,C,A,D;Y_4=C,A,B,D$
过程：

• i = 1 , j = 1 ; x 1 ≠ y 1 ; 则 c [ 1 ] [ 1 ] = max ⁡ { c [ 1 ] [ 0 ] , c [ 0 ] [ 1 ]   = 0 i=1,j=1;x_1\neq y_1;则c[1][1]=\max\{c[1][0], c[0][1]\ = 0 i=1,j=1;x1​=y1​;则c[1][1]=max{c[1][0],c[0][1] =0
• i = 1 , j = 2 ; x 1 ≠ y 2 ; 则 c [ 1 ] [ 2 ] = max ⁡ { c [ 1 ] [ 1 ] , c [ 0 ] [ 2 ] } = 0 i=1,j=2;x_1\neq y_2;则c[1][2]= \max\{c[1][1], c[0][2]\} = 0 i=1,j=2;x1​=y2​;则c[1][2]=max{c[1][1],c[0][2]}=0
• $i=1,j=3;x_1=y_3;则c[1][3]=c[0][2]+1=1$
• i = 1 , j = 4 ; x 1 ≠ y 4 ; 则 c [ 1 ] [ 4 ] = max ⁡ { c [ 0 ] [ 3 ] , c [ 1 ] [ 3 ] } = 1 i=1,j=4;x_1\neq y_4;则c[1][4]= \max\{c[0][3], c[1][3]\} = 1 i=1,j=4;x1​=y4​;则c[1][4]=max{c[0][3],c[1][3]}=1
• $i=2,j=1;x_2=y_1;则c[2][1]=c[1][0]+1=1$
  …依次类推

c矩阵：

b矩阵：

2.2 算法

def lcs_subsequence(x, y):
    m = len(x)
    n = len(y)

    # 创建一个二维表格(m+1)*(n+1),初始值都为0；存储LCS长度即c[i][j]
    dp = [[0] * (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]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                
    # 输出LCS的长度
    lcs_length = dp[m][n]
    print("最长公共子序列 (LCS) 的长度:", lcs_length)

    # 回溯构建LCS
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if x[i - 1] == y[j - 1]:
            lcs.append(x[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    lcs.reverse()
    return lcs

if __name__ == "__main__":
    x = "ACBD"
    y = "ABDA"
    result = lcs_subsequence(x, y)
    print("最长公共子序列 (LCS):", "".join(result))
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
36
37
38
39
40

运行结果：