# Coin Change 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 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

**Example 4:**

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

**Output:** 1

**Example 5:**

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

**Output:** 2

**Constraints:**

`1 <= coins.length <= 12`

`1 <= coins[i] <= 231 - 1`

`0 <= amount <= 104`

Solution:

I solve this problem by using bottom-up approach. It is concept of dynamic programming where we identify the problem and if we see the overlap sub problem nature , we can use either memoization or tabulation approach.

In tabulation approach , we solve smaller problem and with the help of that smaller problem solution , we solve bigger problem until we reach to final solution.

public class Solution {

public int CoinChange(int[] coins, int amount) { // Create an DP array where we will store the solution of subproblem from bottom-up approach.

// As it will have value for 0 also so we will have Amount+1 length; int[] dp = new int[amount + 1];

// Initialize the DP array with sum dummy value. for(int i = 0 ; i < dp.Length ;i++)

{

dp[i] = -99; // You can initialize with any value greater than the "amount" value.

}

dp[0] = 0;

for(int i = 1 ; i < amount+1 ; i++)

{

for(int j = 0 ; j < coins.Length ; j++)

{

if( i-coins[j] >=0)

{

dp[i] = Math.Min(dp[i], 1 + dp[i-coins[j]]);

}

}

}

return dp[amount] == -99 ? -1:dp[amount];

}

}