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

vlambda
2022-03-24

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

"动态规划之最大公共子序列"

今天学习动态规划模块的最后一章, 最大公共子序列

最大公共子序列

最大公共子序列(LCS)是所有序列中最长的子序列, 子序列中元素的位置不需要占用原数列里面连续的位置.

如果S1和S2是两个序列, Z为S1和S2的的子序列, 那么我们称Z为S1和S2的公共子序列. 而且Z必须是依据S1与S2索引的严格递增序列. 严格递增序列指的是Z从原始序列中选择元素的索引是升序的.

如果

S1 = {B, C, D, A, A, C, D}

这时{A, D, B}不是S1的子序列, 因为元素的顺序与S1中的不同(不是严格递增的).

让我们通过通过一个例子来了解最大公共子序列.

如果

S1 = {B, C, D, A, A, C, D}S2 = {A, C, D, B, A, C}

这时公共子序列是

{B, C}, {C, D, A, C}, {D, A, C}, {A, A, C}, {A, C}, {C, D}...等等.

{C, D, A, C}为上面的最大公共子序列. 我们使用动态规划去解决最大公共子序列问题.

使用动态规划解决最大公共子序列

有两个序列:

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

我们使用下面步骤寻找最大公共子序列

1、创建一张(n+1)*(m+1)维度的表, n和m分别是序列X和序列Y的长度. 第一行和第一列我们都记为0.

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

2、开始填充单元格. 如果现在的行和列所对应的字符相匹配, 这时就加1并填充单元格, 并将箭头指向对角线方向.

3、若不是, 则使用前一行与前一列的最大值来填充当前的单元格. 将箭头指向有最大值的单元格. 如果他们相等则指向任意一个.

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

4、重复上面步骤直到单元格填满.

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

5、这张表的最后一行，最后一列的值为最大公共子序列的长度. 这里为2.

6、从最后元素跟着箭头方向开始, 我们寻找最大公共子序列, 看图:

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

为什么动态规划方法比使用递归方法获取最大公共子序列更有效率

动态规划方法减少函数调用的次数. 动态规划存储每个函数执行的结果. 因此后面需要的时候可以直接使用, 不需要重复的调用函数.

在上面的计算中我们把结果存储到一个表中, 以后需要使用的时候直接查即可.

动态规划所花费的时间实际上就是填表的时间, 为O(m*n), 然后递归算法所花费的时间为2max(m, n)指数级的时间了.

最大公共子序列应用

1、压缩基因组重测序数据.

2、通过空中签名在手机内认证用户

最大公共子序列代码

# coding=utf-8
def lcs_algo(S1, S2, m, n): "获取最长公共子序列" L = [[0 for x in range(n + 1)] for x in range(m + 1)]
 # 自底向上的方法创建矩阵 for i in range(m + 1): for j in range(n + 1): if i == 0 or j == 0: L[i][j] = 0 elif S1[i - 1] == S2[j - 1]: L[i][j] = L[i - 1][j - 1] + 1 else: L[i][j] = max(L[i - 1][j], L[i][j - 1]) index = L[m][n] lcs_algo = [""] * (index + 1) lcs_algo[index] = "" # 开始寻找最长公共子序列 i = m j = n while i > 0 and j > 0: if S1[i - 1] == S2[j - 1]: lcs_algo[index - 1] = S1[i - 1] i -= 1 j -= 1 index -= 1 elif L[i - 1][j] > L[i][j - 1]: i -= 1 else: j -= 1 print("S1: " + S1 + "\nS2: " + S2) print("LCS: " + "".join(lcs_algo))

if __name__ == "__main__": S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n)

代码很简单, 理解不成问题. 动态规划模块就到这里了. 下次咱们聊回溯算法.

如果喜欢本文请关注:

vlambda博客
学习文章列表