定義啥的就不多說了，反正我有自己的理解就行。例題是，最長公共子序列和最長公共子字符串的動態規劃求解過程

目錄

一、遞歸和動態規劃? ? ? ??

二、動態規劃求解步驟

三、最長公共子序列

?四、最長公共子字符串

---

一、遞歸和動態規劃? ? ? ??

動態規劃是算法的一種和 ”遞歸“有相似之處，也有不同。動態規劃和分治遞歸，都是為了拆分出更小的子問題，對子問題逐一解決，最后得到結果。兩者不同的地方在于，遞歸的子問題拆分是在代碼實現中體現的，利用棧將大問題拆分成子問題，最后由最小的子問題，逐個反饋合并成大問題所需要的結果。是一個自上而下拆分，再自下而上計算的過程。而動態規劃的子問題的拆分過程并不是在代碼中體現，而是由程序員在編碼前分析好。在編碼時，直接求解最小的問題，通過自下而上的方式解決大問題。

動態規劃相比于"遞歸"的優勢,就是計算效率更高，子問題只需要求解1次就可以。動態規劃的缺點：可能會再空間上增大代價。

例如如下式子：

當計算 f(8) 的值時， 用遞歸的方式就是

f(8) = f(7) +f(6) = ( f(6) + f(5) ) + f(6) ........

用遞歸的方式可以看出，在計算f(8)的值時 f(6) 會被重復計算兩次，再往下 f(5) 會被重復計算3次，以此類推。

而動態規劃的目的就是為了每個子問題最多求解1次，自下而上的方式解決問題就是

f(2) =f(1) + f(0) =1

f(3) =f(2) + f(1) =2

.....

結果如下圖Excel所示

在Excel中展示的求解邏輯，就是動態規劃，每個子問題只需求解1次，自底向上的求解方式。實際上，上圖展示的Excel在代碼中可以在空間上進行優化，只需要用兩個變量分別存儲最新的f(x-1) ,f(x-2) 就行。

二、動態規劃求解步驟

問題抽象化：將一個具體的問題變成一個通用的問題

確認結果變量f(x1,x2.....)和 抽象參數集合{x1,x2,x3......}

分析抽象參數和結果變量的關系

將分析出來的結果整合成遞歸的表達式

根據表達式，作表得到動態規劃的求解過程

*分析過程的優化(本文不具體說明)

三、最長公共子序列

分析字符串X = ABCBDAB? ? 和 Y =BDCABA 的 最長公共子序列(注：序列不是字符串，序列可以不連續)

1.1：問題抽象化

? ? ?分析字符串? ?和 的最長公共子序列

1.2 參數有兩個 Xn? 和 Ym? ?，結果變量有長度 L (n,m)和公共子序列 Z(n,m)。

1.3 如果? 和 的最長子序列是

當??時,那么必然滿足??，且??和的公共子序列為

當 ??????? ， ?時，那么?和Ym的公共子序列為Zk

?當 ??????? ， ?時，那么Xn?和的公共子序列為Zk

1.4因此：

?1.5

長度L的Excel表如下?

最大公共子序列Z的Excel表如下?

?四、最長公共子字符串

分析字符串X = ABABDAB? ? 和 Y =BDCABA 的 最長公共子字符串(即連續的序列)

1.1：問題抽象化

? ? ?分析字符串? ?和 的最長公共子串

1.2 參數有兩個 Xn? 和 Ym? ?，結果變量有長度 L (n,m)和公共子串Z(n,m)。臨時變量，當前在判定的公共子字符串Z'(n,m)，在判定的公共子字符串長度L'(n,m)

1.3 如果? 和 的最長子字符串是

當判和，?當?≠?時?，那么<??,??>必然不是的公共字符串，如果??那么必然滿足?至少是 X，Y長度為1的公共子字符串，如果還滿足,那么至少是 X，Y長度為21的公共子字符串,以此類推...因此

?所以最長公共字符串，就是歷史比較出來的最長公共字符串 和當前作比較公共字符串作對比，如果當前作比較公共字符串比歷史最長的都要長，那么就覆蓋歷史的最長公共子字符串

?如果? 和 的最長子字符串是

L‘(n,m) >= (歷史比較出的)最長字符串長度L(n,m),那么當前比較出的公共子字符串就是最長的??; 如果?L‘(n,m) < L(n,m)? ? ,那么最長公共字符串不變

?

最后得到的結果是ABA

?

總結

以上是生活随笔為你收集整理的动态规划算法分析和理解：最长公共子序列、公共子字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。