動態規劃(Dynamic Programming)


「動態規劃(dynamic programming)」是「分治法(divide and conquer)」的延伸,指將大問題拆解成小問題後,把小問題的答案「記憶化(memoization)」儲存,待下次要再處理相同的小問題時,僅需把儲存的答案取出使用即可,不用重複計算。跟遞迴相比,可節省時間、提升效能;跟貪婪演算法相比,考量得較為全面。


範例一:Longest Common Sequence, LCS (LeetCode 1143.)

「最長共同子序列(Longest Common Sequence, LCS)」指在兩個字串中,按順序出現最長共有字串的長度,該字串的字母不必相連。範例如下:
text1:ABCDE
text2:ACE
LCS(text1, text2) = 3(最長共同子序列 ACE,長度為 3)

LCS 解法一:遞迴

從尾到頭依序比較:

  1. 若兩字串最尾端字母相同:LCS+1,並比較兩字串前一個字母。
  2. 若兩字串最尾端字母相異:一字串去掉最尾端字母、另一字串維持原狀,比較兩字串最尾端字母是否相同,若相同則進入 1.、相異則再持續 2.。

LCS 解法二:動態規劃

在一表格中的橫軸、縱軸分別排列兩字串。

  1. 若上方與左方數字相同:即遞迴的步驟 1.,將對應儲存格中的數字+1,並將箭頭指向左上方,代表既有子序列長度+1。
  2. 若上方與左方數字相異:即遞迴的步驟 2.,比較上方與左方數字,在儲存格中填寫較大者,代表延續既有最長的子序列長度。

往左上箭頭數即 LCS 長度、順著箭頭方向可由尾到頭依序找到 LCS 中的字母。

在上表中,凡是箭頭方向往左上者,皆列入「最長共同子序列」;從數字最大者沿箭頭方向走,就能夠由尾到頭找到「最長共同子序列」為 "ACE"。


範例二:Fibonacci Number (LeetCode 509.)

費氏數列(Fibonacci Number, FB)的定義如下:

  1. FB(0)=0
  2. FB(1)=1
  3. n≥2 時,FB(n)=FB(n-1)+FB(n-2)

費式數列解法一:遞迴

依照定義,依序算到 FB(0)=0 與 FB(1)=1 為止。

若使用遞迴算法,則 FB(3)(黃色部分)計算了 2 次、FB(2)(綠色部分)計算了 3 次,若求的項次更高,則重複計算的部分更多,會大幅增加時間複雜度。

費式數列解法二:動態規劃

FB(2)、FB(3)、FB(4) 都計算過一次後就儲存在記憶體中,要計算 FB(5) 時,只要將原計算 FB(3)、FB(4) 的值取出即可,不需重複計算。


範例三:Multistage Graph

若使用動態規劃尋找最短路徑,則稱為「多階圖網(Multistage Graph)」,彷彿是計算並儲存不同階段的答案後,將這些答案取出,以供後續計算使用。

現有一加權有向圖如下:

要找到 A 到 F 的最短路徑,一樣可以分別透過「遞迴」與「動態規劃」兩方式如下:

最短路徑解法一:遞迴

一一往回到 F 路徑上各節點的最短距離,每一步皆取最短者。

最終可得 A 到 F 的最短路徑為 A→B→D→F,如下圖綠色路徑:

最短路徑解法二:動態規劃(即「Multistage Graph」)

所有已經計算好的路徑長都儲存在表中,需要時直接從表中叫資料。

求得的結果一樣是 A→B→D→F,但在計算過程中,依序由「Stage 1」處理到「Stage 4」,計算後面每個階段時都可以直接取用前面階段的結果。

#演算法 #動態規劃







你可能感興趣的文章

Secure Apache Using Certbot with Let's Encrypt on Ubuntu 20.04

Secure Apache Using Certbot with Let's Encrypt on Ubuntu 20.04

第六天:完成爬蟲

第六天:完成爬蟲

JavaScript 的同步與非同步 - 從 Callback function 到 Promise

JavaScript 的同步與非同步 - 從 Callback function 到 Promise






留言討論