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特訓班目錄 和 學習路徑