使用Python求解LCS（最长公共序列）

1、首先获得打分矩阵：通过动态规划的编程思想，比较两序列的字符，确定打分矩阵中每个元素的数值。

初始化矩阵

c[i,0]=0和c[0,j]=0

计算若两字符相同则c[i,j]=c[i-1,j-1]+1,否则为c[i-1,j],c[i,j-1]的最大值。

2、在计算打分矩阵的同时，加入方向矩阵的生成，方向矩阵一般用于回溯。

代码如下：

def LCS(x,y):

    import numpy as np

    c=np.zeros((len(x)+1,len(y)+1))

    b=np.zeros((len(x)+1,len(y)+1))

    for i in range(1,len(x)+1):

        for j in range(1,len(y)+1):

            if x[i-1]==y[j-1]:

                c[i,j]=c[i-1,j-1]+1

                b[i,j]=2

            else:

                if c[i-1,j]>=c[i,j-1]:

                    c[i,j]=c[i-1,j]

                    b[i,j]=1

                else:

                    c[i,j]=c[i,j-1]

                    b[i,j]=3

    return c,b

3、接下来构建回溯方法：

回溯方法根据方向矩阵的数值，若为2，则表示为共有元素，需要保存，回溯完整个矩阵后，结束，输出结果。

代码如下：

def getLCS(x,y):

    c,b=LCS(x,y)

    i=len(x)

    j=len(y)

    lcs=''

    while i>0 and j>0:

        if b[i][j]==2:

            lcs=x[i-1]+lcs

            i-=1

            j-=1

        if b[i][j]==1:

            i-=1

        if b[i][j]==3:

            j-=1

        if b[i][j]==0:

            break

    return lcs

4、实现算法程序的伪代码如下：