算法课上，需要了解动态规划求lcs问题 ，便做个记录 
参考:动态规划解最长公共子序列(LCS)(附详细填表过程),【Python】最长公共子序列LCS
LCS的定义
最长公共子序列，即Longest Common Subsequence，LCS。
一个序列S任意删除若干个字符得到新序列T，则T叫做S的子序列；
两个序列X和Y的公共子序列中，长度最长的那个，定义为X和Y的最长公共子序列。
例如字符串acdfg与adfc的最长公共子序列为adf，
注意区别最长公共子串(Longest Common Substring)最长公共字串要求连续。
LCS的意义
求两个序列中最长的公共子序列算法，广泛的应用在图形相似处理、媒体流的相似比较、计算生物学方面、查重等。
蛮力法求解最长公共子序列：
需要遍历出所有的可能，时间复杂度是O(n³)
动态规划求解最长公共子序列：
分析规律：
设X=<x1,x2,x3,x4...,xm>，Y=<y1,y2,y3,y4...,yn>为两个序列，Z=<z1,z2,z3,z4...,zk>是他们的任意公共子序列
算法中的数据结构：长度数组
1、如果xm = yn，则zk = xm = yn 且 Zk-1是Xm-1和Yn-1的lcs
2、如果xm != yn 且 zk != xm，则Z是Xm-1和Y的lcs
3、如果xm != yn 且 zk != yn，则Z是X和Yn-1的lcs
所以如果用一个二维数组c表示字符串X和Y中对应的前i，前j个字符的LCS的长度的话，可以得到以下公式：
当 i = 0, 或者j = 0 时 lcs 长度 为0；
当 i >0 且 j > 0 且 x[i] 等于y[j] 时 lcs长度为 c[i-1, j-1] + 1，及左上角值加1；
当 i >0 且 j > 0 且 x[i] 不等于 y[j] 时 lcs长度为 max（ c[I, j - 1], c[i - 1，j]）， 及上方和左方的最大值
算法中的数据结构：方向变量
栗子
时间复杂度：
由于只需要填一个i行j列的二维数组，其中i代表第一个字符串长度，j代表第二个字符串长度
所以时间复杂度为O（i*j）
python 实现
def LCS(s1, s2):
size1 = len(s1) + 1
size2 = len(s2) + 1
# 程序多加一行，一列，方便后面代码编写
chess = [[["", 0] for j in list(range(size2))] for i in list(range(size1))]
for i in list(range(1, size1)):
chess[i][0][0] = s1[i - 1]
for j in list(range(1, size2)):
chess[0][j][0] = s2[j - 1]
print("初始化数据：")
print(chess)
for i in list(range(1, size1)):
for j in list(range(1, size2)):
if s1[i - 1] == s2[j - 1]:
chess[i][j] = ['↖', chess[i - 1][j - 1][1] + 1]
elif chess[i][j - 1][1] > chess[i - 1][j][1]:
chess[i][j] = ['←', chess[i][j - 1][1]]
else:
chess[i][j] = ['↑', chess[i - 1][j][1]]
print("计算结果：")
print(chess)
i = size1 - 1
j = size2 - 1
s3 = []
while i > 0 and j > 0:
if chess[i][j][0] == '↖':
s3.append(chess[i][0][0])
i -= 1
j -= 1
if chess[i][j][0] == '←':
j -= 1
if chess[i][j][0] == '↑':
i -= 1
s3.reverse()
print("最长公共子序列：%s" % ''.join(s3))