python实现最长公共子序列


            最长公共子序列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.递归定义最优值





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('') 





运行结果输出如下：





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

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

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