【动态规划】最长公共子序列——算法设计与分析-Toy模板网

这篇具有很好参考价值的文章主要介绍了【动态规划】最长公共子序列——算法设计与分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、问题定义

1.1 子序列

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

给定序列 $X$ ：

$X ： A BCB D A B$

$X$ 的子序列：

$X_1：ABCBDAB$

$X_2：ABCB$

$X_3：ACBB$

1.2 公共子序列

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

$X ： A BCB D A B$

$Y ： B D C A B A$

公共子序列示例：

$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$ 优化目标： $ma x ∣ 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\leq i_1< i_2<...<i_l\leq n；1\leq j_1<j_2<...<j_l\leq m$

二、求解策略

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

$X ： A BCB D A B$

$Y ： B D C A B A$

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

2.1 分析问题结构

形式化给出问题表示：

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

明确原始问题：

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

2.2 建立递推关系

对于给定序列：

最长公共子序列动态规划算法,算法设计与分析,动态规划,算法,动态规划

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

① $x_i=y_j$

此时，
$C[i,j]=max\left\{\begin{matrix} C[i-1,j-1]+1 & ①\\ C[i-1,j] & ②\\ C[i,j-1] &③ \end{matrix}\right.$
但是， ${①\ge max\left \{ ②，③ \right \} }$ ，因此，
$C [i, j] = C [i - 1, j - 1] + 1$

② $x_i \ne y_j$

此时，
$C[i,j]=max\left\{\begin{matrix} C[i-1,j] & ①\\ C[i,j-1] & ② \end{matrix}\right.$
综上所述，得到递推关系式：
$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.$

2.3 自底向上计算

（1）初始化

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

最长公共子序列动态规划算法,算法设计与分析,动态规划,算法,动态规划

（2）依照递推公式计算

最长公共子序列动态规划算法,算法设计与分析,动态规划,算法,动态规划

2.4 追踪最优方案

构造追踪数组 $rec [1.. n]$ ，用来记录子问题的来源：
$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.$
（使用 $U$ 代表来自上方， $L$ 代表来自左方， $LU$ 代表来自左上角）