最长公共子序列python实现
最长公共子序列是动态规划基本题目，以下依照动态规划基本步骤解出来。1.找出最优解的性质，并刻划其结构特征
序列a共同拥有m个元素，序列b共同拥有n个元素，假设a==b，那么a[:m]和b[:n]的最长公共子序列长度就是a[:m-1]和b[:n-1]的最长公共子序列长度+1；假设a!=b，那么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=[ for j in range(lena+1)]
flag=[ for j in range(lena+1)]
for i in range(lena):
for j in range(lenb):
if a==b:
c=c+1
flag='ok'
elif c>c:
c=c
flag='left'
else:
c=c
flag='up'
return c,flag
def printLcs(flag,a,i,j):
if i==0 or j==0:
return
if flag=='ok':
printLcs(flag,a,i-1,j-1)
print(a,end='')
elif flag=='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。
转载请注明：转自http://blog.iyunv.com/littlethunder/article/details/25637173
页:
[1]