DP動態規劃 深入淺出 以Fibonacci Number 費式數列 為例
Dynamic programming 對初學者似乎是很大的一道門檻。
教科書往往寫得太生硬，用幾行數學式子去代表背後的數學意義，對於剛開始接觸的同學會學得很吃力。
常常想破頭也想不出來，但是看到解答又好像看得懂，但不知道破題的關鍵到底從哪裡跑出來的。
別害怕，筆者也走過同樣的路。 XD
今天會帶領讀者從DP的大原則出發，從簡單的題目開始理解DP解題的精隨與框架。
Dynamic programming本質是透過遞迴關係式，去解決一個大規模的問題，而這個大規模的問題又可以被分解為較小規模的子問題，而且子問題往往彼此重複。
需要複習的話，可以點這篇 究竟什麼是 動態規劃DP?
Dynamic programming的解題框架可分為三大步驟:
1. 定義DP狀態 [我在哪裡]
2. 推導DP狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]
以一個大家耳熟能詳的費式數列拿當作第一道題目破題作為練習。
這篇專欄有一個專屬的解題教學影片，搭配服用，效果更佳。
題目敘述
題目要求我們求出費式數列的第n項，並且已經給定初始條件和遞迴關係式如下:
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
雖然題目已經直接奉送DP所需要的遞迴關係式和初始條件，但這裡我們還是先走過一遍解題框架可分為三大步驟，藉此鞏固解題基礎。
(備註: 遞迴關係式和初始條件往往是要自己推導出來的，特別是在Medium/Hard或者競賽題)
1. 定義DP狀態
[我在哪裡]
這題沒有什麼疑問，直接定義DP[n] = 費式數列的第n項即可。
比較習慣數學符號思考的讀者，可以想成令f(n) = 費式數列的第n項。
2.推導DP狀態轉移關係式(通則)
[我從哪裡來] => [答案從哪裡推導而來]
這裡題目也已經給了，不過就算沒給，我們也知道費式數列的通則就是
費式數列的第n項 = 費式數列的第n-1項 + 費式數列的第n-2項
寫成遞迴關係式就式DP[n] = DP[n-1] + DP[n-2]
比較習慣數學符號思考的讀者，可以想成令f(n) = f(n-1) + f(n-2)
留意，其實到了這一步，我們已經把大規模的問題DP[n]分解成兩個較小規模的子問題DP[n-1]、 DP[n-2]。
並且，我們知道，在得到子問題的答案之後，可以推導出原本所求
DP[n] = DP[n-1] + DP[n-2]
3. 釐清DP初始狀態(終止條件)
[第一步怎麼走，怎麼出發的]
這裡題目已經指定，第零項F(0) = 0, 第一項F(1) = 1。
也就是說DP[0] = 0, DP[1] = 1
比較習慣數學符號思考的讀者，可以想成給定
f(0) = 0 且 f(1) = 1
到這裡，已經填滿解題框架的所有內容，接著我們把它轉成程式碼，
這裡以Python作為示範
程式碼
class Solution:
def fib(self, n: int) -> int:
def dp(n):
## look-up table
if n in table:
return table[n]
## general cases
# DP[n] = DP[n-1] + DP[n-2]
table[n] = dp(n-1) + dp(n-2)
return table[n]
# ---------------------------------
# base case
# DP[0] = 0
# DP[1] = 1
table = {0:0, 1:1}
return dp(n)
複雜度分析
時間複雜度: O( n )
總共有O(n)層呼叫，每層呼叫在O(1)時間內可以計算完。
空間複雜度: O( n )
遞迴深度最深為O( n )，DP table空間所需也為O( n )
下一篇: 一魚多吃 用費式數列的DP模型來解 爬樓梯Climbing Stairs_Leetcode #70
Refernce
[1] Python from Naive method to DP + optimization [w/ Comment]
你可能也想看
