## Coin Change is popular coding interview question.

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`

.

*Read More on Search Engine System Design Interview Question.*

You may assume that you have an infinite number of each kind of coin.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Example 4:**

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

**Example 5:**

Input:coins = [1], amount = 2Output:2

**Constraints:**

`1 <= coins.length <= 12`

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

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

^{4}

Approach Dynamic programming – Bottom up

**Algorithm**

For the iterative solution, we think in bottom-up manner. Before calculating F(i), we have to compute all minimum counts for amounts up to ii. On each iteration i of the algorithm F(i) is computed as min_{j=0…n−1}F(i−c_{j})+1

In the example above you can see that: F(3) = min{F(3−c1),F(3−c2),F(3−c3)}+1 = min{F(3−1),F(3−2),F(3−3)}+1 = min{F(2),F(1),F(0)}+1 = min{1,1,0}+1 = 1

So now we know the steps to solve the coding challenge, let’s add logic together. Here is the working solution!

```
public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
```

```
function coinChange(coins, amount) {
let finalResult = FindMinCount(coins, 0, 0, amount, 0, amount + 1);
function FindMinCount(coins, i, currentSum, amount, count, result) {
if (amount == 0) {
return 0;
}
if (currentSum > amount) {
return result;
}
if (currentSum == amount) {
result = Math.min(count, result)
return result
}
if (i <= coins.length - 1) {
count++;
result = FindMinCount(coins, i, currentSum + coins[i], amount, count, result);
count--;
result = FindMinCount(coins, i + 1, currentSum, amount, count, result);
}
return result;
}
return finalResult
}
```