日韩久久久精品,亚洲精品久久久久久久久久久,亚洲欧美一区二区三区国产精品 ,一区二区福利

最長公共子序列python實現

系統 2025 0

最長公共子序列python實現

1、dp基本思路:

公共子序列最優子結構:
將問題分解表成更簡單的子問題,這個子問題可以分解成更多的子問題使用動態規劃算法求解,這個過程需要在一個表中儲存同一級別的子問題的解,因此這個解可以被更高級的子問題使用。

2、問題的解

定義兩個序列X、Y,二維數組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)當X的第a位于Y的第b位完全相同時為1,否則為0
?此時,f[i][j]中最大的數便是 X和 Y的最長公共子序列的長度,依據該數組回溯,便可找出最長公共子序列。

如:

X = 'helloword'
Y = 'eoskod'

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

該算法的空間、時間復雜度均為O(n^2)} O(n^2)。經過優化后,空間復雜度可為 O(n),時間復雜度可為O(nlogn)。
注:最長公共子序列不要求序列連續

python代碼:

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

def LCSlength(X,Y):
    '''
    輸入:序列X和序列Y
    輸出:X和Y的最長公共子序列長度
    '''
    #定義f數組,每行n個元素,每列m個元素
    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)]
    #定義路徑數組
    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,二維數組,路徑信息
            X,原始序列
            i,j ,遞歸下標
            arr,存儲結果元素
    '''
    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)
            
          

看到網上還有將之轉化成最長上升序列算法求解,思路是轉化為最長上升子序列,并采用二分搜索,這種方法可以把平均時間復雜度降到nlogn,但是存在極端情況效率比普通的動態規劃方法效率更低。先留個坑,后再研究,睡覺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


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 房产| 美姑县| 梁河县| 桂平市| 民丰县| 明星| 稻城县| 天气| 宜春市| 中阳县| 德保县| 武定县| 柞水县| 丹棱县| 桂林市| 左云县| 都匀市| 潞城市| 清新县| 永和县| 防城港市| 穆棱市| 宁德市| 鄂尔多斯市| 磴口县| 贵溪市| 沧州市| 三都| 平乡县| 嘉鱼县| 塘沽区| 清远市| 云和县| 高邮市| 和硕县| 罗源县| 徐闻县| 东方市| 永德县| 平原县| 洛南县|