Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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.

(Click here to read about Bottom-up Dynamic Pro­gram­ming).

  • 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

          Glad it helped .