DP動態規劃 深入淺出 以Coin change最精簡找零 為例
這篇專欄有一個專屬的解題教學影片，搭配服用，效果更佳。
如同這個Dynamic programming 深入淺出系列的開始，在經過比較簡單的暖身題(費式數列)之後，來看進階一點的DP題目
一樣，再次強調DP的解題框架，鞏固知識點。
Dynamic programming本質是透過遞迴關係式，去解決一個大規模的問題，而這個大規模的問題又可以被分解為較小規模的子問題，而且子問題往往彼此重複。
Dynamic programming的解題框架可分為三大步驟
1. 定義狀態 [我在哪裡]
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]
以一個大家耳熟能詳的最精簡零錢找零Coin change來作為練習。
詳細的題目可在這裡看到
https://leetcode.com/problems/coin-change/
題目敘述
題目要求我們求出最精簡的零錢找零數目。範例輸入和輸出如下:
Example 1:
11元可以用最少3個零錢湊出，分別是$5兩枚和$1一枚
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
3元無法用給定的零錢湊出(題目只給兩元銅板)，返回-1
Input: coins = [2], amount = 3
Output: -1
Example 3:
0元不需要找零，返回0
Input: coins = [1], amount = 0
Output: 0
我們還是先走過一遍解題框架可分為三大步驟，藉此鞏固解題基礎。
(備註: 遞迴關係式和初始條件往往是要自己推導出來的，特別是在Medium/Hard或者競賽題)
1. 定義狀態 [我在哪裡]
這題沒有什麼疑問，
直接定義DP[n] =找出n元最精簡的找零零錢數目(用最少數目的銅板湊出)。
比較習慣數學符號思考的讀者，可以想成令f(n) = 找出n元最精簡的零錢數目。
2. 定義狀態轉移關係式(通則)
[我從哪裡來] => [答案從哪裡推導而來]
這裡題目也沒給，不過沒關係，我們可以試者推導看看。
用Example1來幫助我們思考
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
我們最後要求的是DP[11], 也就是11元的最精簡找零零錢數目。
那11元可以怎麼去找零呢? 這裡題目給我們三種銅板，分別是1元、2元、5元銅板。
那麼我們就可以試著用1元、2元、5元銅板去找零
寫成數學式子就是
DP[11] = min( DP[11–1], DP[11–2], DP[11–5]) + 1
= min( DP[10], DP[9], DP[6]) + 1
後面那個+1是什麼呢? 就是代表這次找零我們用了一個銅板(可能是1元、2元、或5元，暫時還不知道，但是總是會從其中裡面選一個)，所以+1
那為什麼要取min最小值呢? 因為題目所求是最精簡的零錢找零數目(最少的銅板數目)
留意，其實到了這一步，我們已經把大規模的問題DP[n]分解成3個較小規模的子問題DP[n-1]、 DP[n-2]、 DP[n-5]。
並且，我們知道，在得到子問題的答案之後，可以推導出原本所求
DP[n] = min(DP[n-1], DP[n-2], DP[n-5]) + 1
寫成遞迴關係式就是DP[n] = min( DP[n-1], DP[n-2], DP[n-5] ) + 1
比較習慣數學符號思考的讀者，可以想成f(n) = min( f(n-1), f(n-2), f(n-5) ) + 1
接著問，那10元怎麼找開呢? 其實一樣，依此類推，我們可以試著用1元、2元、或5元試試看。
寫成數學式子，就是
DP[10] = min( DP[10–1], DP[10–2], DP[10–5]) + 1
= min( DP[9], DP[8], DP[5]) + 1
其他9元, 8元, 7元, ….等依此類推
到這邊，隱約看到一個找零問題的模板，可以寫成一個推廣後的通則，
針對n元，給定k種銅板Ci, i = 1, 2, … , k，最精簡的找零零錢數目如下
DP[n] = min( DP[n — C1 ], …, DP[n — Ck ]) + 1
for every valid coin $C1 to $Ck
3. 釐清初始狀態(終止條件)
[第一步怎麼走，怎麼出發的]
比較細心的讀者可能已經注意到，關鍵就是:
用每個銅板去縮小找零問題的規模，從n元找零問題一直化簡，降到0元的找零問題。
沒錯，正是如此。
但還是有終止條件必須仔細考慮。
降到0元怎麼辦? 0元還能再降下去嗎?不行
0元很明顯是我們這個題目的終止條件之一，當n=0時就不再往下遞迴。
0元的找零方法也很明顯，就是0，代表不拿任何一枚銅板。
降到負的值怎麼辦? 例如計算中可能出現n=4 去用5元銅板找零， 導致遞回到-1，這時該如何處理?
同上面的思考邏輯，合法的n值最小就是0，負的就應該停下來。
那…該回傳什麼值好呢?
考慮到這邊是”最小化”(最少數目的銅板去找零)的問題，我們可以用一個很大的正值或者無窮大，來代表: 這個金額找不開，無法找零”
後續的程式碼，我們選擇用python語法中的無窮大float(‘inf’)來做示範。
到這裡，已經填滿解題框架的所有內容，接著我們把它轉成程式碼，
這裡以Python作為示範
程式碼 Top-down DP + 找零錢DP框架
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
table = {}
def dp( amount ):
if amount < 0:
# base case
return float('inf')
if amount == 0:
# base case
return 0
if amount in table:
# look-up table
return table[amount]
# general cases:
table[amount] = min( dp( amount - coin ) + 1 for coin in coins )
return table[amount]
# ----------------------------------
res = dp(amount)
return -1 if res == float('inf') else res
複雜度分析
時間複雜度: O(cn)
真的n個不同目標金額，用c個銅板去計算最佳找零銅板數量。
空間複雜度: O(n)
DP table紀錄n個不同目標金額的最佳找零銅板數量。
回到DP特訓班目錄 和 學習路徑
你可能也想看
