动态规划查找最大公共子序列
• 使用二维数组C[m,n]
• C[i,j]记录序列Xi和Yj的最长公共子序列的长度
– 当i=0或j=0时,空序列是Xi和Yj的最长公共子序列,故C[i,j]=0
以上X和Y进行一 一对比,
A和B不相等,则比较它的左边那个数和上边那个数他们两谁大
A和D比较,不相等,同理
…
直达A和A相比,相等,则它的左上角那个数+1
以此类推
然后按照图写B、C、B、A
def lcs_len(a,b):
n = len(a)
m = len(b)
l = [([0]*(m+1)) for i in range(n+1)]
for i in range(n+1)[1:]:
for j in range(m+1)[1:]:
if a[i-1]==b[j-1]:
l[i][j]=l[i-1][j-1]+1
else:
l[i][j]=max(l[i-1][j],l[i][j-1])
return l
a = 'ABCBDAB'
b = 'BDCABA'
l = lcs_len(a,b)
for i in l:
print(i)