例如#xff1a;ABCD”和“BDF”都是“ABCDEFG”的子序列。

最长公共子序列(LCS)

给定两个序列X和Y#xff0c;求X和Y长度最大的公共子字列。

例:XABBCBDE”…

序列中的每一个值都有两种选择被选择或者不被选择因此一个长度为n的序列其子序列为种。

求解长度为n和长度为m的序列的公共子序列对比和个子序列之间的关系是否相同因此时间复杂度为O()。

思考:

LCS的最优子结构令X(......和Y(......)为两个序列Z(......)为X和Y的任意

例如序列ABCD和ABC其LCS为ABC此时即D与C不相等则为ABC可见ABC是ABC和ABC的LCS。

例如序列ABC和ACD其LCS为AC此时即D与C不相等则为AC可见AC是ABC和AC的LCS。

示例如下

因此LCS(a,b)应该来源于LCS(a[:-1],b)与LCS(a,b[:-1])中更大的那一个

3问题递推式

x0都是空列表y0也是空列表因此与x0或者y0的LCS一定是0。

序列BDC和序列AC

])和LCS([BD],[A])中图中可看出两者都为0即LCS([BDC],

序列BDCA和序列AA

A则A一定是两个序列的LCS中的一个元素且LCS([BDC],

[A])

x[i-1]其实是字符串的i因为i0在二维列表中都是0不求解但是在字符串中仍需要从索引0遍历c[i][j]

c[i-1][j-1]

x和y的最后一个元素对比完二维数组的最后一位print(lcs_length(ABCBDAB,

BDCABA))

二维数组初始值为0用于存储箭头方向,1表示左上2表示上3表示左for

range(1,m1):

xiyi的情况二维数组中ij0时都为0已经确定但字符串xy仍需从0开始遍历c[i][j]

c[i

二维数组初始值为0用于存储箭头方向,1表示左上2表示上3表示左for

range(1,m1):

xiyi的情况二维数组中ij0时都为0已经确定但字符串xy仍需从0开始遍历c[i][j]

c[i

列表翻转并将列表用连接成字符串print(lcs_trackback(ABCBDAB,

BDCABA))