DP動態規劃 深入淺出 以Fibonacci Number 費式數列 為例

Dynamic programming 對初學者似乎是很大的一道門檻。

教科書往往寫得太生硬，用幾行數學式子去代表背後的數學意義，對於剛開始接觸的同學會學得很吃力。

常常想破頭也想不出來，但是看到解答又好像看得懂，但不知道破題的關鍵到底從哪裡跑出來的。

別害怕，筆者也走過同樣的路。 XD

今天會帶領讀者從DP的大原則出發，從簡單的題目開始理解DP解題的精隨與框架。

Dynamic programming本質是透過遞迴關係式，去解決一個大規模的問題，而這個大規模的問題又可以被分解為較小規模的子問題，而且子問題往往彼此重複。

Dynamic programming的解題框架可分為三大步驟:

1. 定義狀態 [我在哪裡]

2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]

以一個大家耳熟能詳的費式數列拿當作第一道題目破題作為練習。

這篇專欄有一個專屬的解題教學影片，搭配服用，效果更佳。

詳細的題目可在這裡看到

題目要求我們求出費式數列的第n項，並且已經給定初始條件和遞迴關係式如下:

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

雖然題目已經直接奉送DP所需要的遞迴關係式和初始條件，但這裡我們還是先走過一遍解題框架可分為三大步驟，藉此鞏固解題基礎。

(備註: 遞迴關係式和初始條件往往是要自己推導出來的，特別是在Medium/Hard或者競賽題)

1. 定義狀態 [我在哪裡]

這題沒有什麼疑問，直接定義DP[n] = 費式數列的第n項即可。

比較習慣數學符號思考的讀者，可以想成令f(n) = 費式數列的第n項。

2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]

這裡題目也已經給了，不過就算沒給，我們也知道費式數列的通則就是

費式數列的第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. 釐清初始狀態(終止條件) [第一步怎麼走，怎麼出發的]

這裡題目已經指定，第零項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( n ) 遞迴深度最深為O( n )，DP table空間所需也為O( n )

Refernce:

[1] Python from Naive method to DP + optimization [w/ Comment]