(學(xué)習(xí)筆記，無(wú)什參考價(jià)值！)

1 問(wèn)題

2 算法

2.1 Brute-force LCS algorithm

• 檢查每一個(gè)subsequence是否是$y$的子列時(shí)，遍歷$y$的每一個(gè)元素，看是否依次可以全部覆蓋subsequence所有元素，所以其復(fù)雜度為$O(n)$;

2.2 Dynamic-programming hallmark #1

• 動(dòng)態(tài)規(guī)劃的第一特征–最優(yōu)子結(jié)構(gòu)，下面用定理的方式證明這種特征；
  

• 這個(gè)性質(zhì)是說(shuō)，一個(gè)規(guī)模稍大的最優(yōu)解問(wèn)題建立在一些規(guī)模較小的最優(yōu)解問(wèn)題基礎(chǔ)之上，由此解決問(wèn)題的思路就有兩個(gè)方向：自頂向下的遞歸方式、自底向上的方式。
  

• 很容易可以推出下面的（數(shù)量上的）性質(zhì)：
  

• 由上面的遞歸公式，首先想到的是使用遞歸實(shí)現(xiàn)：
  

• 下面用遞歸樹(shù)分析遞歸實(shí)現(xiàn)的時(shí)間復(fù)雜度：
  

• 遞歸樹(shù)的高度就是指數(shù)，所以時(shí)間復(fù)雜度是指數(shù)級(jí)別，和暴力解法沒(méi)有什么大提高！

• 從上面遞歸樹(shù)圖中觀察到一個(gè)現(xiàn)象：遞歸樹(shù)中存在大量重復(fù)的子問(wèn)題，這些是導(dǎo)致遞歸算法龜速的原因，也是動(dòng)態(tài)規(guī)劃誕生的另外一個(gè)必要條件。

2.3 Dynamic-programming hallmark #2

• 動(dòng)態(tài)規(guī)劃的第二特征–大量重復(fù)子問(wèn)題；
  

• 有了這個(gè)特征，此時(shí)有兩條改進(jìn)思路，一是在遞歸過(guò)程中，存儲(chǔ)算過(guò)的每一個(gè)子問(wèn)題。算法描述如下：

• 另外一個(gè)改進(jìn)思路是自底向上算法：
  
• 在上面自底向上的計(jì)算過(guò)程中，同時(shí)做了最優(yōu)數(shù)值記錄和最優(yōu)路徑記錄這兩件事，路徑本質(zhì)是：記錄每一步由哪一個(gè)子問(wèn)題得到父問(wèn)題的解，路徑的起點(diǎn)是(1,1)，終點(diǎn)是(m,n)，從終點(diǎn)到起點(diǎn)依照“來(lái)的時(shí)候做的箭頭標(biāo)記”，可以完整的回到起點(diǎn)，其中路徑中標(biāo)記’↘’路標(biāo)的坐標(biāo)點(diǎn)是最優(yōu)解中的點(diǎn)。
• 手工演示如下：
  

2.4 打印最優(yōu)解

• 依照上面的分析可以很容易找到一個(gè)倒序的LCS，結(jié)合遞歸實(shí)現(xiàn)原理，正好可以正序打印出LCS，算法如下：
  
• 看這段代碼，直覺(jué)上感覺(jué)還是倒序輸出LCS，但是仔細(xì)考慮一下遞歸底層的運(yùn)行過(guò)程，遞歸中的“遞”就是入棧，遞進(jìn)；“歸”就是出棧，回歸，以倒序壓入到棧中，以正序出棧；

3 代碼實(shí)現(xiàn)

# -*- coding: utf-8 -*- import numpy as npdef LCS_LENGTH(X, Y):m = len(X)n = len(Y)b = np.array([0] * (m * n)).reshape((m, n))c = np.array([0] * (m * n)).reshape((m, n))for i in range(1, m):c[i][0] = 0for j in range(0, n):c[0][j] = 0for i in range(1, m):for j in range(1, n):if X[i] == Y[j]:c[i][j] = c[i - 1][j - 1] + 1b[i][j] = 0elif 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] = '-1'return c, bdef PRINT_LCS(b, X, i, j):if i == 0 or j == 0:returnif b[i][j] == 0:PRINT_LCS(b, X, i - 1, j - 1)print(X[i])elif b[i][j] == 1:PRINT_LCS(b, X, i - 1, j)else:PRINT_LCS(b, X, i, j - 1)if __name__ == '__main__':X = ['x', 'A', 'B', 'C', 'B', 'D', 'A', 'B']Y = ['x', 'B', 'D', 'C', 'A', 'B', 'A']c, b = LCS_LENGTH(X, Y)PRINT_LCS(b, X, len(X) - 1, len(Y) - 1)

運(yùn)行結(jié)果：

B C B A

總結(jié)

以上是生活随笔為你收集整理的四、Dynamic-programming algorithm Dynamic--LCS的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。