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
Dynamic programming.
Complete knapsack problem.
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for j in range(coin, amount + 1):
dp[j] += dp[j - coin]
return dp[-1]
class Solution {
public int change(int amount, int[] coins) {
int m = coins.length;
int[][] dp = new int[m + 1][amount + 1];
dp[0][0] = 1;
for (int i = 1; i <= m; ++i) {
for (int j = 0; j <= amount; ++j) {
for (int k = 0; k * coins[i - 1] <= j; ++k) {
dp[i][j] += dp[i - 1][j - coins[i - 1] * k];
}
}
}
return dp[m][amount];
}
}
class Solution {
public int change(int amount, int[] coins) {
int m = coins.length;
int[][] dp = new int[m + 1][amount + 1];
dp[0][0] = 1;
for (int i = 1; i <= m; ++i) {
int v = coins[i - 1];
for (int j = 0; j <= amount; ++j) {
dp[i][j] = dp[i - 1][j];
if (j >= v) {
dp[i][j] += dp[i][j - v];
}
}
}
return dp[m][amount];
}
}
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
dp[j] += dp[j - coin];
}
}
return dp[amount];
}
}
function change(amount: number, coins: number[]): number {
let dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (let coin of coins) {
for (let i = coin; i <= amount; ++i) {
dp[i] += dp[i - coin];
}
}
return dp.pop();
}
func change(amount int, coins []int) int {
dp := make([]int, amount+1)
dp[0] = 1
for _, coin := range coins {
for j := coin; j <= amount; j++ {
dp[j] += dp[j-coin]
}
}
return dp[amount]
}
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1);
dp[0] = 1;
for (auto coin : coins) {
for (int j = coin; j <= amount; ++j) {
dp[j] += dp[j - coin];
}
}
return dp[amount];
}
};