### LeetCode  • ㊗️
• 大家
• offer
• 多多！

## Problem

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 -1.

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 = 
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.


Example 3:

Input: amount = 10, coins = 
Output: 1


Constraints:

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• All the values of coins are unique.
• 0 <= amount <= 5000

## Code

amount = 5, coins = [1,2,5] class Solution {
public int change(int amount, int[] coins) {
int[][] dp = new int[coins.length + 1][amount + 1];

for(int i = 1; i <= coins.length; i++){
dp[i] = 1;
int currCoin = coins[i - 1];

for(int j = 1; j <= amount; j++){
// 少使用一种硬币组成当前 amount 组合数 + 使用当前的硬币组成当前 amount的组合数
dp[i][j] = dp[i - 1][j];

if(j >= currCoin) {
dp[i][j] += dp[i][j - currCoin];
}
}
}

return dp[coins.length][amount];
}
}