最长公共子序列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代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
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。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/littlethunder/article/details/25637173
