一、问题定义

1.1 子序列

子序列是给定序列中在任意位置去掉任意多个字符后得到的结果。例如:

给定序列 X X X:

X : A B C B D A B X:ABCBDAB X:ABCBDAB

X X X的子序列:

X 1 : A B C B D A B X_1:ABCBDAB X1​:ABCBDAB

X 2 : A B C B X_2:ABCB X2​:ABCB

X 3 : A C B B X_3:ACBB X3​:ACBB


1.2 公共子序列

给定两个序列 X X X和 Y Y Y:

X : A B C B D A B X:ABCBDAB X:ABCBDAB

Y : B D C A B A Y:BDCABA Y:BDCABA

公共子序列示例:

X 1 = Y 1 = C A X_1=Y_1=CA X1​=Y1​=CA

X 2 = Y 2 = A B A X_2=Y_2=ABA X2​=Y2​=ABA

X 3 = Y 3 = B C A B X_3=Y_3=BCAB X3​=Y3​=BCAB


1.3 问题形式化定义

最长公共子序列问题:

输入:

\quad 序列 X = < x 1 , x 2 , . . . , x n > X=<x_1,x_2,...,x_n> X=<x1​,x2​,...,xn​>和序列 Y = < y 1 , y 2 , . . . , y m > Y=<y_1,y_2,...,y_m> Y=<y1​,y2​,...,ym​>

输出:

\quad 求解一个公共子序列 Z = < z 1 , z 2 , . . . , z l > Z=<z_1,z_2,...,z_l> Z=<z1​,z2​,...,zl​>

\quad \quad \quad 优化目标: m a x ∣ Z ∣ max|Z| max∣Z∣

\quad \quad \quad 约束条件: < z 1 , z 2 , . . . , z l > = < x i 1 , x i 2 , . . . , x l 1 > = < y j 1 , y j 2 , . . . , y j l > <z_1,z_2,...,z_l>=<x_{i_1},x_{i_2},...,x_{l_1}>=<y_{j_1},y_{j_2},...,y _{j_l}> <z1​,z2​,...,zl​>=<xi1​​,xi2​​,...,xl1​​>=<yj1​​,yj2​​,...,yjl​​>,其中 1 ≤ i 1 < i 2 < . . . < i l ≤ n ; 1 ≤ j 1 < j 2 < . . . < j l ≤ m 1\leq i_1< i_2<...<i_l\leq n;1\leq j_1<j_2<...<j_l\leq m 1≤i1​<i2​<...<il​≤n;1≤j1​<j2​<...<jl​≤m



二、求解策略

给定两个序列 X X X和 Y Y Y:

X : A B C B D A B X:ABCBDAB X:ABCBDAB

Y : B D C A B A Y:BDCABA Y:BDCABA

其最长公共子序列 Z = B D A B Z=BDAB Z=BDAB,观察可以发现,其后3位为长度为3的最长公共子序列,其后2位为长度为2的最长公共子序列,最后一位为长度为一的最长公共子序列。这便启示我们可能存在最优子结构和重叠子问题,可以采用动态规划进行求解。


2.1 分析问题结构

形式化给出问题表示:

  • C [ i , j ] C[i,j] C[i,j]: X [ 1.. i ] X[1..i] X[1..i]和 Y [ 1.. j ] Y[1..j] Y[1..j]的最长公共子序列长度

明确原始问题:

  • C [ n , m ] C[n,m] C[n,m]: X [ 1.. n ] X[1..n] X[1..n]和 Y [ 1.. m ] Y[1..m] Y[1..m]的最长公共子序列长度

2.2 建立递推关系

对于给定序列:

在这里插入图片描述

对于末尾来说,有两种情况:

① x i = y j x_i=y_j xi​=yj​

此时,
C [ i , j ] = m a x { C [ i − 1 , j − 1 ] + 1 ① C [ i − 1 , j ] ② C [ i , j − 1 ] ③ C[i,j]=max\left\{\begin{matrix} C[i-1,j-1]+1 & ①\\ C[i-1,j] & ②\\ C[i,j-1] &③ \end{matrix}\right. C[i,j]=max⎩ ⎨ ⎧​C[i−1,j−1]+1C[i−1,j]C[i,j−1]​①②③​
但是, ① ≥ m a x { ②,③ } {①\ge max\left \{ ②,③ \right \} } ①≥max{②,③},因此,
C [ i , j ] = C [ i − 1 , j − 1 ] + 1 C[i,j]=C[i-1,j-1]+1 C[i,j]=C[i−1,j−1]+1

② x i ≠ y j x_i \ne y_j xi​=yj​

此时,
C [ i , j ] = m a x { C [ i − 1 , j ] ① C [ i , j − 1 ] ② C[i,j]=max\left\{\begin{matrix} C[i-1,j] & ①\\ C[i,j-1] & ② \end{matrix}\right. C[i,j]=max{C[i−1,j]C[i,j−1]​①②​
综上所述,得到递推关系式:
C [ i , j ] = { C [ i − 1 , j − 1 ] + 1 x i = y j m a x { C [ i − 1 , j ] , C [ i , j − 1 ] } x i ≠ y j C[i,j]=\left\{\begin{matrix} C[i-1,j-1]+1 & x_i=y_j\\ max\left\{ C[i-1,j],\\ C[i,j-1] \right\} & x_i\ne y_j\\ \end{matrix}\right. C[i,j]={C[i−1,j−1]+1max{C[i−1,j],C[i,j−1]}​xi​=yj​xi​=yj​​

2.3 自底向上计算

(1)初始化

当其中一段序列长度为0时,最长公共子序列长度为0,即: C [ i , 0 ] = C [ 0 , j ] = 0 C[i,0]=C[0,j]=0 C[i,0]=C[0,j]=0

在这里插入图片描述

(2)依照递推公式计算

在这里插入图片描述


2.4 追踪最优方案

构造追踪数组 r e c [ 1.. n ] rec[1..n] rec[1..n],用来记录子问题的来源:
r e c [ i , j ] = { L U i f C [ i , j ] = C [ i − 1 , j − 1 ] + 1 U i f C [ i , j ] = C [ i − 1 , j ] L i f C [ i , j ] = C [ i , j − 1 ] rec[i,j]=\left\{\begin{matrix} LU & if\quad C[i,j]=C[i-1,j-1]+1\\ U & if\quad C[i,j]=C[i-1,j]\\ L & if\quad C[i,j]=C[i,j-1] \end{matrix}\right. rec[i,j]=⎩ ⎨ ⎧​LUUL​ifC[i,j]=C[i−1,j−1]+1ifC[i,j]=C[i−1,j]ifC[i,j]=C[i,j−1]​
(使用 U U U代表来自上方, L L L代表来自左方, L U LU LU代表来自左上角)

当左值和上值相等时,任取其一即可。

从右下角开始追踪,如果其值为 L L L,则向左移动1格, U U U则向上移动一格, L U LU LU向左上角移动一格。当且仅当 r e c [ i , j ] = L U rec[i,j]=LU rec[i,j]=LU时, X [ i ] = Y [ j ] X[i]=Y[j] X[i]=Y[j]为最长公共子序列中的一个字符,记录下来。如此寻找,直至抵达 r e c rec rec数组的边界。


2.5 算法实例

给定序列 X X X和 Y Y Y:

在这里插入图片描述

初始化辅助数组:

在这里插入图片描述

计算完毕:

在这里插入图片描述

追踪最优方案:

在这里插入图片描述

得到最长公共子序列 B C B A BCBA BCBA



三、算法分析

3.1 伪代码

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述


3.2 时间复杂度

时间复杂度 O ( n m ) O(nm) O(nm)

Logo

有“AI”的1024 = 2048,欢迎大家加入2048 AI社区

更多推荐