序列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]的最长公共子序列长度）。
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('') 
