個(gè)人主頁：丷從心

系列專欄：動(dòng)態(tài)規(guī)劃算法

問題描述

• 給定兩個(gè)序列 X = { ? x 1 , x 2 , ? ? , x m ? } X = \set{x_{1} , x_{2} , \cdots , x_{m}} X={x1?,x2?,?,xm?}和 Y = { ? y 1 , y 2 , ? ? , y n ? } Y = \set{y_{1} , y_{2} , \cdots , y_{n}} Y={y1?,y2?,?,yn?}，找出$X$和$Y$的最長公共子序列

最長公共子序列的結(jié)構(gòu)

• 設(shè)序列 X = { ? x 1 , x 2 , ? ? , x m ? } X = \set{x_{1} , x_{2} , \cdots , x_{m}} X={x1?,x2?,?,xm?}和 Y = { ? y 1 , y 2 , ? ? , y n ? } Y = \set{y_{1} , y_{2} , \cdots , y_{n}} Y={y1?,y2?,?,yn?}的最長公共子序列為 Z = { ? z 1 , z 2 , ? ? , z k ? } Z = \set{z_{1} , z_{2} , \cdots , z_{k}} Z={z1?,z2?,?,zk?}
  • 若$x_m=y_n$，則$z_k=x_m=y_n$，且$Z_{k?1}$是$X_{m?1}$和$Y_{n?1}$的最長公共子序列
  • 若$x_m\ne y_n$且$z_k\ne x_m$，則$Z$是$X_{m?1}$和$Y$的最長公共子序列
  • 若$x_m\ne y_n$且$z_k\ne y_n$，則$Z$是$X$和$Y_{n?1}$的最長公共子序列

子問題的遞歸結(jié)構(gòu)

• 當(dāng)$x_m=y_n$時(shí)，找出$X_{m?1}$和$Y_{n?1}$的最長公共子序列，然后在其尾部加上$x_m$
• 當(dāng)$x_m\ne y_n$時(shí)，找出$X_{m?1}$和$Y$的一個(gè)最長公共子序列及$X$和$Y_{n?1}$的一個(gè)最長公共子序列，這兩個(gè)公共子序列中較長者即為$X$和$Y$的最長公共子序列

$c[i][j]$遞歸方程

c [ i ] [ j ] = { 0 , i = 0 或 j = 0 c [ i ? 1 ] [ j ? 1 ] + 1 , i , j > 0 ; x i = y j max ? { ? c [ i ] [ j ? 1 ] , c [ i ? 1 ] [ j ] ? } , i , j > 0 ; x i ≠ y j c[i][j] = \begin{cases} 0 , & i = 0 或 j = 0 \\ c[i - 1][j - 1] + 1 , & i , j > 0 ; x_{i} = y_{j} \\ \max\set{c[i][j - 1] , c[i - 1][j]} , & i , j > 0 ; x_{i} \neq y_{j} \end{cases} c[i][j]=? ? ??0,c[i?1][j?1]+1,max{c[i][j?1],c[i?1][j]},?i=0或j=0i,j>0;xi?=yj?i,j>0;xi?=yj??文章來源地址http://www.zghlxwxcb.cn/news/detail-829929.html

時(shí)間復(fù)雜性

• 由于每個(gè)數(shù)組單元的計(jì)算耗費(fèi)$O(1)$時(shí)間，因此算法耗時(shí)$O(mn)$

構(gòu)造最長公共子序列

• 在算法$LCS$中，每次遞歸調(diào)用使$i$或$j$減$1$，因此算法的計(jì)算時(shí)間為$O(m+n)$

Python實(shí)現(xiàn)

def longest_common_subsequence(str_1, str_2):
    m = len(str_1)
    n = len(str_2)

    # 創(chuàng)建一個(gè)二維數(shù)組來存儲(chǔ)子問題的解
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 填充二維數(shù)組
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str_1[i - 1] == str_2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 構(gòu)造最長公共子序列
    lcs = ''

    i, j = m, n
    while i > 0 and j > 0:
        if str_1[i - 1] == str_2[j - 1]:
            lcs = str_1[i - 1] + lcs

            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return lcs


str_1 = 'ABCDGH'
str_2 = 'AEDFHR'

lcs = longest_common_subsequence(str_1, str_2)

print(f'最長公共子序列: {lcs}')

最長公共子序列: ADH

算法的改進(jìn)

• 如果只需要計(jì)算最長公共子序列的長度，則只用到數(shù)組$c$的第$i$行和第$i?1$行
• 因此，用兩行的數(shù)組空間就可以計(jì)算出最長公共子序列的長度，可將空間需求減至 O ( min ? { ? m , n ? } ) O(\min\set{m , n}) O(min{m,n})

到了這里，關(guān)于【動(dòng)態(tài)規(guī)劃】最長公共子序列Python實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！