最长公共连续子序列和最长公共子序列

最长公共序列：

A[1,3,5,2,5,3,4,5]  长度为m

B:[3,4,2,1,5]           长度为n

则它们的最长公共子序列为3,2,5

我们用LCS（xi,yj）来表示xi和yj的最长公共子序列的长度

那么当xi = yj时，我们就可以把xi和yj都往前移动一步来进行探索

即LCS（xi,yj） = LCS（xi-1,yj-1）+1

如果不相等，则要么把x往前移动一步，要么把y往前移动一步，看谁更大

即LCS(xi,yj) = max(LCS（xi-1,yj）,LCS(xi,yj-1))

综上if xi == yj:

           LCS（xi,yj） = LCS（xi-1,yj-1）+1

        else:

            LCS(xi,yj) = max(LCS（xi-1,yj）,LCS(xi,yj-1))

如果要求这个最长子序列是什么

那么我们就追根溯源

i = m-1 ,j = n-1

s = ""

while i >= 0 and j >= 0:                  #只要有一个为0就停止

    if xi == yj:

        s += xi

    else:

        if   LCS（xi-1,yj）>LCS（xi,yj-1）:

                i    -=   1

         else:

                j      -=   1

return s[::-1]

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------如果是连续子序列问题

我们就换个思路，我们的关注点就应该在连续上面

其实画一个m*n的矩阵，只有在连续的这些对角线上才有值，且值是递增的

所以，我们可以用一个不一样的角度的dp方程来表达

dp[i][j] = 0          如果i == 0  and  j  ==  0

dp[i][j]   =    dp[i-1][j-1]  +  1             xi == yj

dp[i][j]  =  0                                xi    !=    yj