**Physical Address**

304 North Cardinal St.

Dorchester Center, MA 02124

You are given an integer array `coins`

representing coins of different denominations and an integer `amount`

representing a total amount of money.

Return *the fewest number of coins that you need to 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.

**Example 1:**

```
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
```

**Example 2:**

```
Input: coins = [2], amount = 3
Output: -1
```

**Example 3:**

```
Input: coins = [1], amount = 0
Output: 0
```

**Constraints:**

`1 <= coins.length <= 12`

`1 <= coins[i] <= 2`

^{31}- 1`0 <= amount <= 10`

^{4}

```
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int Max = amount + 1;
vector<int> dp(amount + 1, Max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.size(); j++) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
```

```
public class Solution {
public int coinChange(int[] coins, int amount) {
if(amount<1) return 0;
return helper(coins, amount, new int[amount]);
}
private int helper(int[] coins, int rem, int[] count) { // rem: remaining coins after the last step; count[rem]: minimum number of coins to sum up to rem
if(rem<0) return -1; // not valid
if(rem==0) return 0; // completed
if(count[rem-1] != 0) return count[rem-1]; // already computed, so reuse
int min = Integer.MAX_VALUE;
for(int coin : coins) {
int res = helper(coins, rem-coin, count);
if(res>=0 && res < min)
min = 1+res;
}
count[rem-1] = (min==Integer.MAX_VALUE) ? -1 : min;
return count[rem-1];
}
}
```

```
class Solution(object):
def coinChange(self, coins, amount):
MAX = float('inf')
dp = [0] + [MAX] * amount
for i in xrange(1, amount + 1):
dp[i] = min([dp[i - c] if i - c >= 0 else MAX for c in coins]) + 1
return [dp[amount], -1][dp[amount] == MAX]
```

In our experience, we suggest you solve this Coin Change LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Coin Change LeetCode Solution

I hope this Coin Change LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

**More Coding Solutions >>**