動態規劃（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」，計算後面每個階段時都可以直接取用前面階段的結果。