python 最大子序列,最长子序列算法 python

　　Python-求解两个字符串的最长公共子序列

　　一、问题描述

　　给定两个字符串，求解这两个字符串的最长公共序列。比如字符串1:BDC ABA；2: abcb dab。那么这两个字符串的最长公共子序列长度是4，最长公共子序列是BCBA。

　　二、算法求解

　　这是一个动态编程的话题。对于可以用动态规划求解的问题，一般有两个特点：最优子结构；重叠子问题

　　最佳子结构

　　设X=(x1，x2，xn)和Y=(y1，y2，ym)是两个序列，并将X和Y的最长公共子序列记录为LCS(X，Y)

　　寻找LCS(X，Y)是一个最优化问题。因为，我们需要找到X和Y中最长的公共子序列，要找到X和Y的LCS，首先考虑X的最后一个元素和Y的最后一个元素

　　(1)如果xn=ym，即x的最后一个元素与y的最后一个元素相同，则意味着这个元素一定在一个公共子序列中。因此，现在我们只需要找到：LCS(Xn-1，Ym-1)

　　LCS(Xn-1，Ym-1)是原问题的子问题。为什么叫问题？因为它的规模比原问题小。

　　为什么是最优子问题？因为我们在寻找Xn-1和Ym-1的最长公共子序列。最长的！换句话说，最好的一个。

　　(2)如果xn！=ym，这个有点麻烦，因为它产生了两个子问题：LCS(Xn-1，ym)和LCS(Xn，Ym-1)

　　因为序列X和序列Y的最后一个元素不相等，这意味着最后一个元素不能是最长公共子序列中的元素。

　　LCS(Xn-1，Ym)意味着可以在(x1，x2，xn-1)和(y1，y2，ym)。

　　LCS(Xn，Ym-1)意味着可以在(x1，x2，xn)和(y1，y2，ym-1)。

　　通过求解上述两个子问题，谁得到最长的公共子序列，谁就是LCS(X，Y)。数学上，它是：

　　LCS=马克斯{LCS(Xn-1，Ym)，LCS(Xn，Ym-1)}

　　因为条件(1)和(2)考虑了所有可能的情况。因此，我们成功地将原问题转化为三个更小的问题。

　　相关：《Python视频教程》

　　重叠子问题

　　重叠问题是什么？也就是说，原问题转化为子问题后，子问题中还有相同的问题。

　　原问题是：LCS(X，Y)。有LCS (xn-1，ym-1) LCS (xn-1，ym) LCS (xn，ym-1)

　　乍一看，这三个问题并不重叠。但本质上是重叠的，因为只是重叠了很大一部分。示例：

　　第二子问题：LCS(Xn-1，Ym)包含问题LCS(Xn-1，Ym-1)。为什么？

　　因为，当Xn-1和Ym的最后一个元素不同时，我们需要把LCS(Xn-1，Ym-1)分解成LCS(Xn-1，Ym-1)和LCS(Xn-2，Ym)

　　也就是说，在子问题的不断分解中，有些问题是重叠的。

　　因为像LCS这样的问题具有子问题重叠的性质，所以用递归来解决它是不划算的。为了采用递归，中国反复求解子问题，需要注意的是所有子问题的和都是指数级的。

　　那么问题来了。如果用递归求解，会有指数级的子问题，所以时间复杂度是指数级的。这个指数子问题用动态规划变成多项式时间了吗？

　　关键是采用动态规划时，不需要逐个计算重叠的子问题。或者，使用动态规划后，有些子问题直接通过“查表”得到，而不是重新计算。比如：比如求Fib序列。

　　求解fib(5)被分解成两个子问题：fib(4)和fib(3)。求解fib(4)和fib(3)时，分解出一系列小问题。

　　从图中可以看出，根的左右子树有很多重叠：fib(4)和fib(3)！例如，对于fib(2)，它总共出现三次。如果用递归求解，fib(2)会计算三次，而用DP(动态规划)动态规划，fib(2)只计算一次，另外两次直接用“查表”得到。更何况，重点是：找到这个问题的解决方案后，就不需要继续分解问题了。对于递归，问题被连续求解，直到分解成一个基准问题(fib(0)或fib(1))。

　　说到这里，写下最长公共子序列的递归形式才算完整。

　　C[i，j]表示(x1，x2，xi)和(y1，y2，yj)。公式的具体解释请参考《算法导论》章动态编程。

　　三、LCS Py

　　thon代码实现

#!/usr/bin/envpython3
　　#-*-coding:utf-8-*-
　　#Note:用于实现求解两个字符串的最长公共子序列
　　deflongestCommonSequence(str_one,str_two,case_sensitive=True):
　　"""
　　str_one和str_two的最长公共子序列
　　:paramstr_one:字符串1
　　:paramstr_two:字符串2（正确结果）
　　:paramcase_sensitive:比较时是否区分大小写，默认区分大小写
　　:return:最长公共子序列的长度
　　"""
　　len_str1=len(str_one)
　　len_str2=len(str_two)
　　#定义一个列表来保存最长公共子序列的长度，并初始化
　　record=[[0foriinrange(len_str2+1)]forjinrange(len_str1+1)]
　　foriinrange(len_str1):
　　forjinrange(len_str2):
　　ifstr_one[i]==str_two[j]:
　　record[i+1][j+1]=record[i][j]+1
　　elifrecord[i+1][j]>record[i][j+1]:
　　record[i+1][j+1]=record[i+1][j]
　　else:
　　record[i+1][j+1]=record[i][j+1]
　　returnrecord[-1][-1]
　　if__name__=='__main__':
　　#字符串1
　　s1="BDCABA"
　　#字符串2
　　s2="ABCBDAB"
　　#计算最长公共子序列的长度
　　res=longestCommonSequence(s1,s2)
　　#打印结果
　　print(res)#4

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

相关文章阅读