# Dynamic Programming — Minimum Coin Change Problem

Objec­tive: Given a amount ‘A’ and n coins,   v1<v2<v3<.….……<vn . Write a pro­gram to find out min­i­mum num­bers 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 solu­tion with both the options and then choose the opti­mal one, here in this case, select the min­i­mum among all the solutions.

First we will break the prob­lem into smaller prob­lems. So what are our smaller problems.

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

Say MC(j) rep­re­sents the min­i­mum num­ber of coins required to make change of amount j.

Smaller Prob­lems:

• Select 1st coin (value = v1), Now Smaller prob­lem is min­i­mum num­ber of coins required to make change of amount( j-v1), MC(j-v1)
• Select 2st coin (value = v2), Now Smaller prob­lem is min­i­mum num­ber of coins required to make change of amount( j-v2), MC(j-v2)
• Like­wise to up to N
• Select nth coin (value = vn), Now Smaller prob­lem is min­i­mum num­ber of coins required to make change of amount( j-v1), MC(j-vn).

We need to find the min­i­mum num­ber of coins required to make change for j amount. So we will select the min­i­mum of all the smaller prob­lems and add 1 to it because we have select one coin. Now smaller prob­lems will be solved recursively.

So if we write our recur­sive equation

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

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

Using Recur­sion: Every coin has 2 options, to be selected or not selected so

Time Com­plex­ity: O(cn) which is very high.

We can reduce the Time Com­plex­ity sig­nif­i­cantly by using Dynamic programming.

Using Bottom-Up Dynamic Programming.

• We will main­tain an array to store the opti­mal solu­tions for the smaller prob­lems, say we call it as coin­Req[]. length of this array will be amount+1. (starts with 0).
• So coinReq[n] will be our final answer, min­i­mum no of coins required to make change for amount ‘n’.
• Since we are using Bottom-up approach, so will start fill­ing the coin­Req[] from 0 to n. we will start solv­ing it from the smaller pos­si­ble amount which is 0 here.
• We need 0 coins to make change for amount 0, so coinReq[0]=0.
• We will use another array CC[] (size = num­ber of coins )will store the solu­tion for amount n with using all the coins, min­i­mum of all these will the opti­mal solu­tion for the amount.
• Since we are find­ing the solu­tion for all the amounts 0 to N, we have to reset CC[] every time ( for amount = 1 to N)
• See the pro­gram for bet­ter explanation.

Code:

Out­put:

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

#### You may also like...

• Sameos K.

Hello, your recur­sive func­tion is not work­ing for the input (8,[4,5,9]), your func­tion gives 1 as an out­put which is wrong

• Abhi­lash Kumar

run­ning the pro­gram for amount = 1, gives out­put = –1

• Bala

Yes you are cor­rect, it gives out­put = –1 for amount =1;

I think in line 34, the con­di­tion should for ( j = 0 .… ) rather than for( j = 1.…)

• Preet Raj

pub­lic sta­tic 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 min­Coins is always going to be the Coef­fi­cient after divid­ing the amount with the max coin. Thoughts?Am I miss­ing some­thing here?

• tuto­ri­al­hori­zon

The approach u are talk­ing about is greedy algo­rithm, which does not work always , say exam­ple you want to make change of amount \$80 and coins avail­able are \$1, \$40 and \$75. By your approach your answer would be one coin of 75 and 5 coins of \$1 but cor­rect answer would be 2 coins of \$40.

• Preet Raj

Got it. My bad, I didn’t check it for all pos­si­ble sce­nar­ios. Thanks for the example.

• tuto­ri­al­hori­zon

• Sne­ha­sis Ghosh

Great expla­na­tion. But the code is unnec­es­sar­ily com­plex. The attached is a sim­pler code and also gives the actual coins as the out­put.

• gau­rav

at recur­sive solu­tion : MC(j) = Mini=1 to n[MC(j-vi)] +1. Why we are adding 1 here?

While mak­ing amount 2 and given coins are only 1,2. Then com­bi­na­tion 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 min­i­mum of above sub prob­lems is 1.
If we are also adding 1 more to this as per above for­mula we are get­ting 2 which is incor­rect.
Ans is here min­i­mum no of coins to make amount 2 with coins {1,2} is only 1 which is coin {2}.

• Avish Goel

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 min­i­mum of above sub prob­lems is 0.
Then by adding 1,we get the min. num­ber of coins i.e 1 to make amount 2 with coins {1,2}