DDR爱好者之家

python实现最长公共子序列
站长资源 2024/11/26 佚名
52 1538
DDR爱好者之家 Design By 杰米

最长公共子序列python实现，最长公共子序列是动态规划基本题目，下面按照动态规划基本步骤解出来。

1.找出最优解的性质，并刻划其结构特征

序列a共有m个元素，序列b共有n个元素，如果a[m-1]==b[n-1]，那么a[:m]和b[:n]的最长公共子序列长度就是a[:m-1]和b[:n-1]的最长公共子序列长度+1；如果a[m-1]!=b[n-1]，那么a[:m]和b[:n]的最长公共子序列长度就是MAX（a[:m-1]和b[:n]的最长公共子序列长度，a[:m]和b[:n-1]的最长公共子序列长度）。

2.递归定义最优值

python实现最长公共子序列

3.以自底向上大方式计算出最优值

python代码如下：

def lcs(a,b): 
  lena=len(a) 
  lenb=len(b) 
  c=[[0 for i in range(lenb+1)] for j in range(lena+1)] 
  flag=[[0 for i in range(lenb+1)] for j in range(lena+1)] 
  for i in range(lena): 
    for j in range(lenb): 
      if a[i]==b[j]: 
        c[i+1][j+1]=c[i][j]+1 
        flag[i+1][j+1]='ok' 
      elif c[i+1][j]>c[i][j+1]: 
        c[i+1][j+1]=c[i+1][j] 
        flag[i+1][j+1]='left' 
      else: 
        c[i+1][j+1]=c[i][j+1] 
        flag[i+1][j+1]='up' 
  return c,flag 
 
def printLcs(flag,a,i,j): 
  if i==0 or j==0: 
    return 
  if flag[i][j]=='ok': 
    printLcs(flag,a,i-1,j-1) 
    print(a[i-1],end='') 
  elif flag[i][j]=='left': 
    printLcs(flag,a,i,j-1) 
  else: 
    printLcs(flag,a,i-1,j) 
     
a='ABCBDAB' 
b='BDCABA' 
c,flag=lcs(a,b) 
for i in c: 
  print(i) 
print('') 
for j in flag: 
  print(j) 
print('') 
printLcs(flag,a,len(a),len(b)) 
print('')

python实现最长公共子序列

运行结果输出如下：

python实现最长公共子序列

4.根据计算最优值得到的信息，构造最优解

上图是运行结果，第一个矩阵是计算公共子序列长度的，可以看到最长是4；第二个矩阵是构造这个最优解用的；最后输出一个最优解BCBA。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

DDR爱好者之家 Design By 杰米
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
DDR爱好者之家 Design By 杰米
ddrfans.com DDR爱好者之家
8,675无损音乐
1,324高清电影
213破解软件
70,141收录资讯

稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！

昨天有一位朋友在大神群里分享，自己亚服账号被封号之后居然弹出了国服的封号信息对话框。

这里面让他访问的是一个国服的战网网址，com.cn和后面的zh都非常明白地表明这就是国服战网。

而他在复制这个网址并且进行登录之后，确实是网易的网址，也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情，因为以前都没有出现这样的情况，现在突然提示跳转到国服战网的网址，是不是说明了简体中文客户端已经开始进行更新了呢？

更新日志

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网
DDR爱好者之家 Design By 杰米