給定不同面額的硬幣和一個總金額。寫出函數來計算可以湊成總金額的硬幣組合數。假設每一種面額的硬幣有無限個。
示例 1:
輸入: amount = 5, coins = [1, 2, 5]
輸出: 4
解釋: 有四種方式可以湊成總金額:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
輸入: amount = 3, coins = [2]
輸出: 0
解釋: 只用面額2的硬幣不能湊成總金額3。
示例 3:
輸入: amount = 10, coins = [10]
輸出: 1
注意:
你可以假設：
- 0 <= amount (總金額) <= 5000
- 1 <= coin (硬幣面額) <= 5000
- 硬幣種類不超過 500 種
- 結果符合 32 位符號整數
解題思路
數組定義
dp[i]代表金額為i時的組合數
狀態轉移
遍歷所有金額的情況，當前金額i，可能由金額i-coin的情況轉移而來
dp[i]+=dp[i-coin];
因為最外層循環遍歷了所有硬幣，所以可以排除了重復的組合數
代碼
class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0]=1;for (int coin : coins) {for (int i=coin;i<=amount;i++){dp[i]+=dp[i-coin];}}return dp[amount];}
}
