一、題目介紹
今天要解的題目是LeetCode的Coin Change

題目會給我們一組不同面額的硬幣，以及一個目標金額amount
每種硬幣可以使用任意次數，要求找出組成目標金額所需要的最少硬幣數量

例如
coins = [1,2,5]
amount = 11

可以使用5 + 5 + 1 = 11
總共需要3枚硬幣
因此答案為3

如果
coins = [2]
amount = 3
因為只有面額2的硬幣，無法組成3
因此答案為-1，代表無法組成目標金額

二、解題思路
這題可以使用Dynamic Programming

我們先定義dp[i]
代表：組成金額i所需要的最少硬幣數量

例如：coins = [1,2,5]
我們可以逐步計算
dp[0] = 0
dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 2
dp[5] = 1
...
其中dp[0] = 0
因為組成金額0不需要任何硬幣

三、狀態轉移公式
假設現在要計算dp[i]

如果最後使用一枚面額為coin的硬幣，那麼在使用這枚硬幣之前，我們其實已經需要先組成i - coin

而組成i - coin所需要的最少硬幣數量就是dp[i - coin]

再加上現在這一枚硬幣dp[i - coin] + 1

因此我們可以對所有硬幣進行比較dp[i] = min(dp[i], dp[i - coin] + 1)

四、實際範例
coins = [1,2,5]
amount = 11

我們可以從 0 開始逐步計算

例如計算11
可以使用
1 + dp[10]
2 + dp[9]
5 + dp[6]

對應的硬幣數量
1 + 2 = 3
1 + 3 = 4
1 + 2 = 3

因此dp[11] = 3
最後答案就是3

五、為什麼需要設定「無限大」？
一開始我們並不知道每個金額最少需要幾枚硬幣
因此可以先將DP陣列初始化成一個很大的數字，代表目前還不知道這個金額能不能組成

例如：amount + 1
因為最差情況下，如果有1元硬幣，最多也只需要amount枚
所以amount + 1可以作為一個不可能的初始值

例如：dp = [0, amount + 1, amount + 1, ...]
之後再利用每一種硬幣逐步更新最小值

六、Java實作

七、Python實作

八、DP的計算流程
以以下為例
coins = [1,2,5]
amount = 5

dp[1]
可以使用一枚1元硬幣：dp[1] = 1

dp[2]
可以直接使用一枚2元：dp[2] = 1

dp[3]
可以1 + 2
所以dp[3] = 2

dp[4]
可以2 + 2
所以dp[4] = 2

dp[5]
可以直接使用5
因此dp[5] = 1
最後dp = [0,1,1,2,2,1]

答案為1

九、時間與空間複雜度
假設：amount = A
而硬幣種類數量為：n
我們需要對每個金額檢查每一種硬幣

因此時間複雜度為：O(A × n)
也就是O(amount × coins.length)

DP陣列需要保存amount + 1個狀態
因此空間複雜度為：O(amount)

十、Java與Python解法比較

十一、實作結果
Leetcode測試結果：Accepted

十二、今日學習心得
今天學習 Coin Change，讓我對 Dynamic Programming 有了更進一步的理解。

前兩天的DP題目中，Day 17 的 Climbing Stairs 是利用前兩個狀態計算目前狀態；Day 18 的 House Robber 則是比較「選擇目前項目」與「不選擇目前項目」的結果。

到了今天的 Coin Change，我需要思考的是：如果最後選擇一枚硬幣，那麼在使用這枚硬幣之前，需要先解決哪一個更小的問題？

例如要組成 11 元，如果最後使用 5 元硬幣，那麼前面就必須先組成 6 元。

因此：dp[11] = dp[6] + 1

再比較使用不同面額硬幣所得到的結果，最後取最小值。

這讓我了解到，DP 最重要的不只是建立陣列，而是要先找出狀態定義與狀態轉移關係。

另外，這題也讓我學到如何處理「無法達成目標」的情況。可以先將狀態設定成一個不可能的數值，最後再判斷是否仍然維持這個狀態。

今天最大的收穫是：面對 DP 問題時，可以從「最後一步做了什麼」開始反推，找出完成目前問題之前必須先解決的子問題。