DP動態規劃 深入淺出 以Coin change II 找零方法數 為例

如同這個Dynamic programming 深入淺出系列的開始，在經過比較簡單的入門題(Coin Change)之後，來看進階一點的DP題目Coin Change II

不免俗，再次強調DP的解題框架，鞏固知識點。

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

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

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

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

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

題目敘述  Coin Change II

給定銅板陣列coins，和目標金額amount。
要求我們計算找零組合方法總數。

測試範例

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作為示範

程式碼 DP動態規劃

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 )

關鍵知識點 找零錢DP框架

強烈建議跟著複習相關的Coin Change I 和 演算法框架統整:

合縱連橫: 找零錢的DP框架_理解背後的本質、

觸類旁通: 用 DFS回溯法框架 解 組合數之和 Combination sum 全系列題。

去鞏固知識點，強化理解與認識、加深印象。

Reference

[1] Python/JS/Go/C++ O(cn) DP // Unbounded Knapsack [w/ Visualization]

回到DP特訓班目錄 和 學習路徑