【动态规划】最长公共子序列——算法设计与分析_最长公共子序列动态规划算法

---

一、问题定义

1.1 子序列

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

给定序列$X$：

$X：ABCBDAB$

$X$的子序列：

$X_1：ABCBDAB$

$X_2：ABCB$

$X_3：ACBB$

1.2 公共子序列

给定两个序列$X$和$Y$：

$X：ABCBDAB$

$Y：BDCABA$

公共子序列示例：

$X_1=Y_1=CA$

$X_2=Y_2=ABA$

$X_3=Y_3=BCAB$

1.3 问题形式化定义

最长公共子序列问题：

输入：

\quad 序列$X=<x_1,x_2,...,x_n>$和序列$Y=<y_1,y_2,...,y_m>$

输出：

\quad 求解一个公共子序列$Z=<z_1,z_2,...,z_l>$

\quad \quad \quad 优化目标：$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}>$，其中$1\le i_1<i_2<...<i_l\le n；1\le j_1<j_2<...<j_l\le m$

---

二、求解策略

给定两个序列$X$和$Y$：

$X：ABCBDAB$

$Y：BDCABA$

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

2.1 分析问题结构

形式化给出问题表示：

• $C[i,j]$：$X[\mathrm{1..}i]$和$Y[\mathrm{1..}j]$的最长公共子序列长度

明确原始问题：

• $C[n,m]$：$X[\mathrm{1..}n]$和$Y[\mathrm{1..}m]$的最长公共子序列长度

2.2 建立递推关系

对于给定序列：

对于末尾来说，有两种情况：

①$x_i=y_j$

此时，
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$$

②$x_i\ne y_j$

此时，
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$

（2）依照递推公式计算

2.4 追踪最优方案

构造追踪数组$rec[\mathrm{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$代表来自上方，$L$代表来自左方，$LU$代表来自左上角）

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

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

2.5 算法实例

给定序列$X$和$Y$：

初始化辅助数组：

计算完毕：

追踪最优方案：

得到最长公共子序列$BCBA$

---

三、算法分析

3.1 伪代码

3.2 时间复杂度

时间复杂度$O(nm)$