# Dynamic Programming – Minimum Coin Change Problem

Objective: Given a amount ‘A’ and n coins,   v1<v2<v3<………..<vn . Write a program to find out minimum numbers of coins required to make the change for the amount ‘A’.

Example:

```Amount: 5

Coins [] = 1, 2, 3.

No of ways to make the change are : { 1,1,1,1,1} , {1,1,1,2}, {2,2,1},{1,1,3} and {3,2}.

So as we can see minimum number of coins required are 2 ( 3+2=5}.
```

Approach:

For Every coin we have two options, whether so select it or don’t select it. So we can find out the solution with both the options and then choose the optimal one, here in this case, select the minimum among all the solutions.

First we will break the problem into smaller problems. So what are our smaller problems.

Amount is A and coins are v1, v2, …….,vn.

Say MC(j) represents the minimum number of coins required to make change of amount j.

Smaller Problems:

• Select 1st coin (value = v1), Now Smaller problem is minimum number of coins required to make change of amount( j-v1), MC(j-v1)
• Select 2st coin (value = v2), Now Smaller problem is minimum number of coins required to make change of amount( j-v2), MC(j-v2)
• Likewise to up to N
• Select nth coin (value = vn), Now Smaller problem is minimum number of coins required to make change of amount( j-v1), MC(j-vn).

We need to find the minimum number of coins required to make change for j amount. So we will select the minimum of all the smaller problems and add 1 to it because we have select one coin. Now smaller problems will be solved recursively.

So if we write our recursive equation

## MC(j) = Mini=1 to n[MC(j-vi)] +1

NOTE: Before selecting the coin, make sure whether value of the coin is less than equal to amount needed.

Using Recursion: Every coin has 2 options, to be selected or not selected so

Time Complexity: O(cn) which is very high.

We can reduce the Time Complexity significantly by using Dynamic programming.

Using Bottom-Up Dynamic Programming.

• We will maintain an array to store the optimal solutions for the smaller problems, say we call it as coinReq[]. length of this array will be amount+1. (starts with 0).
• So coinReq[n] will be our final answer, minimum no of coins required to make change for amount ‘n‘.
• Since we are using Bottom-up approach, so will start filling the coinReq[] from 0 to n. we will start solving it from the smaller possible amount which is 0 here.
• We need 0 coins to make change for amount 0, so coinReq=0.
• We will use another array CC[] (size = number of coins )will store the solution for amount n with using all the coins, minimum of all these will the optimal solution for the amount.
• Since we are finding the solution for all the amounts 0 to N, we have to reset CC[] every time ( for amount = 1 to N)
• See the program for better explanation.

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class MinCoinChange { public int minCoinDynamic(int amount, int[] coins) { // this will store the optimal solution // for all the values — from 0 to given amount. int[] coinReq = new int[amount+1]; coinReq = 0; // 0 coins are required to make the change for 0 // now solve for all the amounts for (int amt = 1; amt <= amount; amt++) { coinReq[amt] = Integer.MAX_VALUE; // Now try taking every coin one at a time and pick the minimum for (int j = 0; j < coins.length; j++) { if (coins[j] <= amt) { // check if coin value is less than amount // select the coin and add 1 to solution of (amount-coin value) coinReq[amt] = Math.min(coinReq[amt – coins[j]] + 1,coinReq[amt]) ; } } } //return the optimal solution for amount return coinReq[amount]; } public static void main(String[] args) { int[] coins = { 1, 2, 3 }; int amount = 20; MinCoinChange m = new MinCoinChange(); System.out.println("(Dynamic Programming) Minimum Coins required to make change for " + amount + " are: " + m.minCoinDynamic(amount, coins)); } }

Output:

```(Dynamic Programming) Minimum Coins required to make change for 20 are: 7
```

### 12 thoughts on “Dynamic Programming – Minimum Coin Change Problem”

1. Hello, your recursive function is not working for the input (8,[4,5,9]), your function gives 1 as an output which is wrong

2. running the program for amount = 1, gives output = -1

• Yes you are correct, it gives output = -1 for amount =1;

I think in line 34, the condition should for ( j = 0 …. ) rather than for( j = 1….)

3. public static int minimumCoins(int amount,int[] coins){
Arrays.sort(coins);
int max = coins[coins.length-1];
int minCoins=amount/max;

int result = minCoins+1;
return result;
}

Can’t this be solved this way? where minCoins is always going to be the Coefficient after dividing the amount with the max coin. Thoughts?Am I missing something here?

• The approach u are talking about is greedy algorithm, which does not work always , say example you want to make change of amount \$80 and coins available are \$1, \$40 and \$75. By your approach your answer would be one coin of 75 and 5 coins of \$1 but correct answer would be 2 coins of \$40.

• Got it. My bad, I didn’t check it for all possible scenarios. Thanks for the example.

• 4. Great explanation. But the code is unnecessarily complex. The attached is a simpler code and also gives the actual coins as the output.

5. at recursive solution : MC(j) = Mini=1 to n[MC(j-vi)] +1. Why we are adding 1 here?

While making amount 2 and given coins are only 1,2. Then combination for (J-v1)

sub prob A. min no of coin (1) to make amount of 2 is: {1,1}=2
sub prob B. min no of coin (2) to make amount of 2 is: {2}=1

Finally minimum of above sub problems is 1.
If we are also adding 1 more to this as per above formula we are getting 2 which is incorrect.
Ans is here minimum no of coins to make amount 2 with coins {1,2} is only 1 which is coin {2}.

• sub-problems would be like this :

sub prob A. min no of coin (1) to make amount of (2-1)=1 is: {1}=1
sub prob B. min no of coin (2) to make amount of (2-2)=0 is: {}=0

Finally minimum of above sub problems is 0.
Then by adding 1,we get the min. number of coins i.e 1 to make amount 2 with coins {1,2}

6. • 