最長公共子序列python實(shí)現(xiàn)

1、dp基本思路：

公共子序列最優(yōu)子結(jié)構(gòu)：
將問題分解表成更簡單的子問題，這個(gè)子問題可以分解成更多的子問題使用動(dòng)態(tài)規(guī)劃算法求解，這個(gè)過程需要在一個(gè)表中儲存同一級別的子問題的解，因此這個(gè)解可以被更高級的子問題使用。

2、問題的解

定義兩個(gè)序列X、Y，二維數(shù)組f[i][j]表示X的i位和Y的j位之前的最長公共子序列長度，
則有
?f[1][1] = same(1,1)
?f[i][j] = max(f[i-1][j-1]+same(i,j),f[i-1][j],f[i][j-1)

其中same(i,j)表示X[i]==Y[j]
?same(a,b)當(dāng)X的第a位于Y的第b位完全相同時(shí)為1，否則為0
?此時(shí)，f[i][j]中最大的數(shù)便是 X和 Y的最長公共子序列的長度，依據(jù)該數(shù)組回溯，便可找出最長公共子序列。

如：

X = 'helloword'
Y = 'eoskod'

X，Y的最長公共子序列長度為4，最長公共子序列為'eood'

該算法的空間、時(shí)間復(fù)雜度均為O(n^2)} O(n^2)。經(jīng)過優(yōu)化后，空間復(fù)雜度可為 O(n),時(shí)間復(fù)雜度可為O(nlogn)。
注：最長公共子序列不要求序列連續(xù)

python代碼：

            
              UP_LEFT = 0		#左上
UP = 1			#上
LEFT = 2		#左

def LCSlength(X,Y):
    '''
    輸入：序列X和序列Y
    輸出：X和Y的最長公共子序列長度
    '''
    #定義f數(shù)組，每行n個(gè)元素，每列m個(gè)元素
    m = len(X)
    n = len(Y)
    #lf = (lambda x,y:x+1 if x>y else y+1)
    #size = lf(m,n)
    f = [[0 for x in range(n+1)] for y in range(m+1)]
    #定義路徑數(shù)組
    path = [[-1 for x in range(n+1)] for y in range(m+1)]

    for i in range(1,m+1):
        for j in range(1,n+1):
            if(X[i-1] == Y[j-1]):
               f[i][j] = f[i-1][j-1]+1
               path[i][j] = UP_LEFT
            else:
               #f[i][j] = max(f[i-1][j],f[i][j-1])
                if(f[i-1][j]>f[i][j-1]):
                    f[i][j] = f[i-1][j]
                    path[i][j] = UP
                else:
                    f[i][j] = f[i][j-1]
                    path[i][j] = LEFT
    return f[m][n],path

def getpath(path,X,i,j,arr):
    '''
        回溯求子序列
        輸入：path,二維數(shù)組，路徑信息
            X，原始序列
            i,j ,遞歸下標(biāo)
            arr，存儲結(jié)果元素
    '''
    if(i==0 or j ==0):
        return
    elif(path[i][j] == UP_LEFT):
        getpath(path,X,i-1,j-1,arr)
        arr.append(X[i-1])
    elif(path[i][j]==UP):
        getpath(path,X,i-1,j,arr)
    elif(path[i][j]==LEFT):
        getpath(path,X,i,j-1,arr)
    else:
        pass
        

X=[1,3,1,4,5]
Y=[1,1,1,4,5]

#X = 'helloword'
#Y = 'eoskod'
    
arr = []
length,path = LCSlength(X,Y)
getpath(path,X,len(X),len(Y),arr)
print(length)
print(arr)
            
          

看到網(wǎng)上還有將之轉(zhuǎn)化成最長上升序列算法求解，思路是轉(zhuǎn)化為最長上升子序列，并采用二分搜索，這種方法可以把平均時(shí)間復(fù)雜度降到nlogn，但是存在極端情況效率比普通的動(dòng)態(tài)規(guī)劃方法效率更低。先留個(gè)坑，后再研究，睡覺zzz

參考：

https://blog.csdn.net/v_JULY_v/article/details/6110269#commentsedit

https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97