518. Coin Change II ⭐
Medium
You are given an integer array
coins
representing coins of different denominations and an integer amount
representing a total amount of money.Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return
0
.You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
Example 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
Constraints:
1 <= coins.length <= 300
1 <= coins[i] <= 5000
- All the values of
coins
are unique. 0 <= amount <= 5000
func change(amount int, coins []int) int {
dp := make([][]int, len(coins) + 1)
for i:=0; i<len(coins) + 1; i++ {
dp[i] = make([]int, amount + 1)
}
dp[0][0] = 1
for i, coin := range coins {
for j:=0; j<=amount; j++ {
dp[i + 1][j] += dp[i][j]
if j - coin >= 0 {
dp[i + 1][j] += dp[i + 1][j - coin]
}
}
}
return dp[len(dp) - 1][len(dp[0]) - 1]
}