518 - Coin Change (動態規劃)
題目需求
規定有一個要湊出來的金額 amount，然後有一袋硬幣 coins，硬幣面額有限但數量無限，請問有多少湊法？
舉例來說，就是如果有 1、2、5 三種面額的硬幣，要湊成 5 元可以有幾種湊法，答案是 4 種：
官方範例
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
題目解答
const change = function(amount, coins) {
const dp = new Array(amount + 1).fill(0)
dp[0] = 1
for (const coin of coins) {
for (let i = coin; i <= amount; i++) {
dp[i] += dp[i - coin]
}
}
return dp[amount]
}
解析
本題採用動態規劃解法，依照這篇文章的說法，很多時候動態規劃是解決重疊子問題的最佳解，也就是在解決一個複雜問題的過程中，該問題被分解成許多較小的子問題，且這些子問題之間不是完全獨立的，有很多子問題會被重複計算多次。
解析本題解題流程：
- 建立了一個長度為
amount + 1的陣列 dp，它是用來儲存湊成金額 i 的方法數量的陣列。因為還沒開始更新，所以先把值都設為 0。
const dp = new Array(amount + 1).fill(0)
- 建立了一個陣列後，把
dp[0]設為 1，這裡的意思很簡單，就是湊成金額 0 的方法只有一個，就是都不拿任何硬幣。
dp[0] = 1
- 開始第一遍遍歷 (coin = 1)，我們計算出使用硬幣面額 1 去湊出目標金額 i (1 ~ 5) 的方法有幾種。答案是都是一種，因為 1 = 1、2 = 1 + 1、3 = 1+ 1 + 1...以此類推，所以現在我們的陣列是：
dp = [1, 1, 1, 1, 1, 1]
- 接下來必須看一下內部的迴圈，所謂
dp[i] = dp[i] + dp[i-coin]，它的含義是將當前金額 i 之前（考慮當前硬幣面額之前）的組合數（即dp[i]）加上新增加的這個硬幣面額 coin 後能夠組成的額外組合數（即dp[i - coin]）。：
for (let i = coin; i <= amount; i++) {
dp[i] += dp[i - coin]
}
但為何是 dp[i-coin]？
這是因為如果你有一種方式可以組成金額 i - coin，那麼只需要再加上一個面額為 coin 的硬幣，就可以組成金額 i。因此，組成金額 i 的方式數量應該增加組成金額 i - coin 的方式數量，而這個 i-coin 的值都可以從前一次迭代中拿到。
