DP動態規劃 深入淺出 以Coin change II 找零方法數 為例
如同這個Dynamic programming 深入淺出系列的開始，在經過比較簡單的入門題(Coin Change)之後，來看進階一點的DP題目Coin Change II
不免俗，再次強調DP的解題框架，鞏固知識點。
Dynamic programming本質是透過遞迴關係式，去解決一個大規模的問題，而這個大規模的問題又可以被分解為較小規模的子問題，而且子問題往往彼此重複。
Dynamic programming的解題框架可分為三大步驟
1. 定義狀態 [我在哪裡]
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
3. 釐清初始狀態(也可以說是遞迴的終止條件) [第一步怎麼走，怎麼出發的]
詳細的題目可在這裡看到
題目要求我們求出所有的零錢找零組合數目。範例輸入和輸出如下:
Example 1:
5 元總共有4種找零方法，分別是
5元銅板一枚
2元銅板兩枚+1元銅板一枚
2元銅板兩枚+1元銅板三枚
1元銅板五枚
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10]
Output: 1
我們還是先走過一遍解題框架可分為三大步驟，藉此鞏固解題基礎。
1. 定義狀態 [我在哪裡]
這題如果寫過Coin change的人，可能會有一個直接的想法:
Easy, 這題就是前一提的變形，用類似的定義，改成相加就好。
乍看沒問題，但是我們是著走過一個小例子，看看會遇到什麼情況。
定義DP[n] = n元零錢找零組合數目。
假設只有兩種銅板$1和$2，問: 找開3元有幾種組合數
DP[0] = 1 顯然0元只有一種找零組合數: 所有銅板都不拿
DP[1] = 1 顯然1元只有一種找零組合數: $1銅板一枚
DP[2] = DP[2-1] + DP[2–2] = DP[1] + DP[0] = 1 + 1 = 2
2元有兩種找零組合數: $1銅板兩枚 或 $2銅板一枚
恩…so far so good 看起來沒問題，但真的是如此嗎?
繼續看下去，看n=3的時候會發生什麼事
DP[3] = DP[3–1] + DP[3–2] = DP[2] + DP[1] = 2 + 1 = 3
這個錯的DP演算法告訴我們有3元有三種找零組合數。
但是，其實3元只有兩種找零組合數:
$1銅板3枚 或
$1銅板1枚和 $2銅板1枚
那為什麼上面的DP算法會出現三枚呢?
因為上面那種定義無形中已經考慮排列，
但是題目只要求組合數目，所以出現了重複計算的情狀。
DP[3]
= DP[3 - 1] (註: 這個-1代表用$1銅板一枚來湊最後一步) +
DP[3 - 2] (註:這個-2代表用$2銅板一枚來湊最後一步)
= DP[2]+ DP[1]
打開來看，看裡面發生了什麼事
DP[2] = $1銅板兩枚 或 $2銅板一枚 (+ $1銅板一枚來湊最後一步)
=> “$1銅板三枚” 或 “$2銅板一枚 + $1銅板1枚”
DP[1] = $1銅板一枚 (+用$2銅板一枚來湊最後一步)
=> “$1銅板一枚 + $2銅板一枚”
仔細看標粗體的地方，“$2銅板一枚 + $1銅板1枚” 和 “$1銅板一枚 + $2銅板一枚”其實是同一種組合，在DP[2]這條路徑被計入一次，在DP[1]這條路徑又被記入一次，重複了！
所以原本這個定義是錯的，不能使用。
那該怎麼辦呢?
其實，DP也不限定只能一維，我們可以引入一個新的維度，代表銅板的index，一但考慮過，就前往下一個銅板的index，避免重複計算。
DP[ coinIdx, n]: 代表考慮當下這個銅板coins[coinIdx]，湊出n元的組合數
2. 定義狀態轉移關係式(通則) [我從哪裡來] => [答案從哪裡推導而來]
這裡題目也沒給，不過沒關係，我們可以試者推倒看看。
用剛剛的小範例幫助我們思考
Input: amount = 3 coins =[1,2]
Output: 2
3元的找零組合數
= 使用兩元銅板的3元的找零組合數 + 不使用兩元銅板的3元的找零組合數
再往下展開
= 使用兩元銅板和使用一元銅板的3元的找零組合數 +
使用兩元銅板但不使用一元銅板的3元的找零組合數 +
不使用兩元銅板但使用一元銅板的3元的找零組合數 +
不使用兩元銅板也不使用一元銅板的3元的找零組合數
= $2銅板一枚 $1銅板1枚 +
無法找開 +
$1銅板3枚 +
無法找開
所以，總共就是兩種:
$2銅板一枚 $1銅板1枚, 或 $1銅板3枚 去找開3塊錢
輸出為2
推廣到通則就是
DP(coinIdx, n )
= DP( coinIdx-1, n ) + DP( coinIdx, n — coins[coinIdx] )
= 不使用coins[coinIdx]元銅板的n元的找零組合數 + 使用coins[coinIdx]元銅板的n元的找零組合數
3. 釐清初始狀態(終止條件) [第一步怎麼走，怎麼出發的]
終止條件滿明顯的，
就是n=0 (0塊錢)，和n<0負數(因為負的幣值無法找零)的狀態。
0塊錢找零只有一種方法，就是不拿任何一枚銅板，return 1。
負的幣值無法找零，找零組合數為0，return 0
另外，負的coinIdx，代表沒有提供零錢去找零，
很顯然，沒有提供零錢也無法找零，找零組合數也為0，return 0
到這裡，已經填滿解題框架的所有內容，接著我們把它轉成程式碼，
這裡以Python作為示範
程式碼:
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
table = {}
def dp( coinIdx, n ):
if n == 0:
# base case
# Change for $0, only one way to do so by taking nothing
return 1
if (coinIdx < 0) or (n < 0):
# base cases
# Cannot make change without valid coins
# Cannot make change to negative values
return 0
if (coinIdx, n) in table:
# look-up table
return table[ (coinIdx, n) ]
# general cases
table[ (coinIdx, n) ] = dp( coinIdx-1, n ) + dp( coinIdx, n - coins[coinIdx] )
return table[ (coinIdx, n) ]
# ---------------------------------
return dp( len(coins)-1, amount)
時間複雜度:
O( c * n ) 零錢本身一個維度，amount被找開的金額本身又是另一個維度。
空間複雜度:
O( c * n ) 零錢本身一個維度，amount被找開的金額本身又是另一個維度。
DP table 所耗費空間剛好就是一張二維的表格，O( c * n )
等價的迭代寫法(Iterative implementation):
輔助思考的圖解範例
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
# base case:
# amount 0's method count = 1 (by taking no coins)
change_method_count = [1] + [ 0 for _ in range(amount)]
# make change with current coin, from small coin to large coin
for cur_coin in coins:
# update change method count from small amount to large amount
for small_amount in range(cur_coin, amount+1):
# current small amount can make changed with current coin
change_method_count[small_amount] += change_method_count[small_amount - cur_coin]
return change_method_count[amount]
時間複雜度:
O( c * n ) 零錢本身一個維度，amount被找開的金額本身又是另一個維度。
空間複雜度:
O( n ) amount被找開的金額本身是一個維度。
change_method_count 所耗費空間剛好就是一張一維的表格，O( n )
Reference:
[1] Python/JS/Go/C++ O(cn) DP // Unbounded Knapsack [w/ Visualization]
