518 Coin Change 2
518. Coin Change 2
1. Question
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Note:You can assume that
0 <= amount <= 5000
1 <= coin <= 5000
the number of coins is less than 500
the answer is guaranteed to fit into 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
2. Implementation
(1) 完全背包
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int j = 0; j < coins.length; j++) {
for (int i = 1; i <= amount; i++) {
if (coins[j] <= i) {
dp[i] += dp[i - coins[j]];
}
}
}
return dp[amount];
}
}
3. Time & Space Complexity
完全背包: 时间复杂度O(n * amount), 空间复杂度O(amount)
Last updated
Was this helpful?