#！一个序列S任意删除若干个字符得到的新序列T，则T叫做S的子序列
注意，这个和最长公共字串不一样，最长公共子串要求连续。
1.算法公式：
def lcs(a,b): lena = len(a) lenb = len(b) c=[[0]*(lenb+1) for j in range(lena+1) ] flag = [[0]*(lenb+1) for j in range(lena+1) ] for i in range(lena+1)[1:]: for j in range (lenb+1)[1:]: if a[i-1]==b[j-1]: c[i][j]=c[i-1][j-1]+1 flag[i][j]=‘ok‘ elif c[i-1][j]>c[i][j-1]: c[i][j]=c[i-1][j] flag[i][j]=‘left‘ else: c[i][j]=c[i][j-1] return c a=lcs("ABCDEF","DBAFCDF") print(a[-1][-1])
这里只是返回最大长度，如果求最大子序列，还需要进行回溯。
原文：https://www.cnblogs.com/students/p/10335438.html