1 最长公共子序列长度
def lcs(x,y,m,n):
c = [[0]*(n+1)]*(m+1)
print(len(c),len(c[0]))
for i in range(m):
for j in range(n):
if x[i]==y[j]:
c[i+1][j+1]=c[i][j]+1
else:
c[i+1][j+1]=max(c[i+1][j],c[i][j+1])
return c[m][n]
x = [1,3,2,5,6]
y = [6,3,2,4,5,7,6]
m,n = 5,7
print(lcs(x,y,m,n))
变形有最短编辑距离
2 最长上升子序列长度
def lis(x,m): if m == 0: return 0 c = [1]*m #c[i]为以i下标为结尾的最长上升子序列长度，如果m不为0，那么结果至少为1 for i in range(m): for j in range(i): if x[i]>x[j]: c[i] = max(c[j]+1,c[i]) return max(c) x = [2,1,5,7,10,4] m = 6 print(lis(x,m))
3
原文：https://www.cnblogs.com/dylan9/p/8944701.html