究竟什麼是 動態規劃DP?
動態規劃Dynamic Programming其實是
一種泛用的演算法思考方式與演算法建構框架。
動態規劃並不拘束於只能解課本上特定的的範例題。
只要我們能找出DP狀態定義、DP遞迴結構、初始條件(終止條件)，就能適用動態規劃來解題，以數學的形式表達，並且在紙筆上或者電腦上、計算機上計算得到答案。
最直接白話的解釋
白話的說，其實DP動態規劃就是一種問題化簡的技巧，
幫助我們把大規模的題目化簡到小規模的題目，解開小題目的解，把小題目的解儲存起來避免重複計算，並且由小規模的題目反推大規模題目的答案，最終得到原本大規模題目的解。
就好像一句成語說的:「大事化小，小事化無。」
大問題化簡到小問題 就好比 大事化小。
小問題透過查表或者初始條件得到答案，就相當於 小事化無。
(犧牲)空間換取時間(進步)的策略
敏銳的讀者可能已經發現，DP的外表其實和DFS形式實現的遞迴function很像。
但是具體差別在哪裡呢?
DP同樣也有遞迴定義，但是多了隨身記事本
(課本會把隨身記事本稱之為DP table, 或 memoization記憶化的搜索)
DP = Recursion definition 遞迴定義 + Table 紀錄答案的表格
相當於 DFS + memoization
DP動態規劃演算法在遞迴的過程中，
會把每一次當下計算到的答案連同傳入參數一起存起來，
這樣當之後遇到重複的函式呼叫時，就會直接查表返回答案，
避免冗餘不必要的重複計算。
這邊想一下，假如暴力搜索展開費式數列。
例如計算F(100)，是不是比較小的那幾項都要重複計算好幾遍?
在思考建構DP演算法時，通常有一個基本框架可以遵循:
DP演算法建構框架
- 定義DP狀態。
DP[i]代表原題目什麼情況下的解。 - 推導DP狀態轉移關係式(也可稱為DP遞迴關係式)。
DP[i]如何遞迴化簡到更小規模的問題DP[j] - 釐清DP狀態的初始條件(或終止條件)。
DP[ 初始條件 ] =?
通常是最小規模的幾個問題 或者是 問題的最後邊界，
而且可以紙筆計算或者人為推理出答案。
如果上述三個條件都具備了，就代表DP演算法的數學形式已經確立。
接下來只要把演算法轉成對應的程式碼，就可以透過電腦進行驗證和計算答案。
實際案例與對照
如果用大家熟知的費式數列來說
通常，老師或教科書會給出如下的定義
F(n) = F(n-1) + F(n-2) , n >= 2
F(0) = 0
F(1) = 1
那麼對應到DP動態規劃的觀點，怎麼看呢?
DP狀態定義 DP[n] 就相當於F(n)，費式數列的第n項。
DP狀態轉移關係式 相當於 DP[n] = DP[n-1] + DP[n-2]
費式數列的第n項 = 前兩項的和 = 費式數列的第n-1項 + 費式數列的第n-2項
DP狀態的初始條件就相當於最小規模的幾個問題 或者是 問題的最後邊界
DP[0] = 0
DP[1] = 1
定義費式數列的第零項 = 0
定義費式數列的第一項 = 1
求DP[n]也就是費式數列的第n項，
即便n很大，我們還是可以透過遞迴化簡到已知項，
最後再從已知項反推計算得到DP[n] 也就是費式數列的第n項。
這篇的目標是先讓讀者對於DP有初步的了解與認識，下一篇文章會開始用費式數列來作為整個DP特訓班系列的開頭，解說DP演算法框架的思考流程和步驟。
下一篇: DP動態規劃 深入淺出 以Fibonacci Number 費式數列 為例
求解費式數列第n項的DP程式碼
class Solution:
def fib(self, n: int) -> int:
# DP table with F(0) = 0, F(1) = 1
dp = {0: 0, 1: 1}
def getFib( i ):
if i in dp:
return dp[i]
dp[i] = getFib(i-1) + getFib(i-2)
return dp[i]
# ----------------------------------------
return getFib(n)
Reference
[1] Wiki: 動態規劃
