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 — Coin Change Problem

Objec­tive: Given a set of coins and amount, Write an algo­rithm to find out how many ways we can make the change of the amount using the coins given.

This is another prob­lem in which i will show you the advan­tage of Dynamic pro­gram­ming over recursion.

Exam­ple:

Amount = 5

coins [] = {1,2,3}

Ways to make change = 5

{1,1,1,1,1} {1,1,1,2}, {1,2,2}, {1,1,3} {2,3}

Approach:

Recur­sive Solution:

  • We can solve it using recursion.
  • For every coin we have an option to include it in solu­tion or exclude it.
  • See the Code

Code:

Time Com­plex­ity : 2n

I have been asked that by many read­ers that how the com­plex­ity is 2^n . So includ­ing a sim­ple explanation–

For every coin we have 2 options, either we include it or exclude it so if we think in terms of binary, its 0(exclude) or 1(include). so for exam­ple if we have 2 coins, options will be 00, 01, 10, 11. so its 2^2. for n coins , it will be 2^n. In all these options we will be check­ing whether that selec­tion has made the change which is required.

But if we notice that we are solv­ing many sub-problems repeatedly.

We can do bet­ter by apply­ing Dynamic programming.

Dynamic Pro­gram­ming: Bottom-up -

Ear­lier we have seen “Min­i­mum Coin Change Prob­lem”. This prob­lem is slightly dif­fer­ent than that but approach will be bit similar.

Cre­ate a solu­tion matrix. (solution[coins+1][amount+1]).

Base Cases:

  • if amount=0 then just return empty set to make the change, so 1 way to make the change.
  • if no coins given, 0 ways to change the amount.

Rest of the cases:

  • For every coin we have an option to include it in solu­tion or exclude it.
  • check if the coin value is less than or equal to the amount needed, if yes then we will find ways by includ­ing that coin and exclud­ing that coin.
  1. Include the coin: reduce the amount by coin value and use the sub prob­lem solu­tion (amount-v[i]).
  2. Exclude the coin: solu­tion for the same amount with­out con­sid­er­ing that coin.
  • If coin value is greater than the amount then we can’t con­sider that coin, so solu­tion will be with­out con­sid­er­ing that coin.

Equa­tion:

solution[coins+1][amount+1]

= 0 if i=0
solution[i][j] = 1 if j=0
= solution[i — 1][j] + solution[i][j — v[i — 1]] if(coin[i]<=j)
= solution[i — 1][j]; if(coin[i]>j)

Exam­ple:

Amount = 5
coins [] = {1,2,3}

Coin Change Problem

Code:

 Output:

By Dynamic Programming 5

You may also like...