CODEWITHSUNDEEP
dynamic-programming
bitshiftleft
bitshiftleft

Reputation: 23

Coin change,dynamic programming revisited

I am having tough time in understanding the logic behind this problem, This is classical Dynamic Programming Problem

     Coin Change is the problem of finding the number 
     of ways of making changes for a particular amount of cents, n, 
     using a given set of denominations d1,d2,..dm;

I know how the recursion works,Like taking the mth coin or not.But I don't understand what does '+' do between the two states.

For eg

        C(N,m)=C(N,m-1)+C(N-dm,m)
                       ^
                       |

Question might be stupid but I still would like to know so that I can have better understanding.Thanks

Upvotes: 1

Views: 1079

Answers (1)

Shubham Sharma
Shubham Sharma

Reputation: 839

Well , you haven't written your state right! Coin Change:

Let C(i,j) represents the number of ways to form j as a sum using only i coins (from i to 1).

Now to get a recursive function you have to define transitions or change in state or may be just expressing the given expression in the terms of lower values!!

There are 2 independent ways in which I can represent this state that are

1) Lets pick up the i th coin , Then what happens ? I need denomination j-Denomination[i] with i-1 coins if repetition is not allowed . i.e. C(i,j)= C(i-1,j-Denominations[i])

But wait , we are missing some ways i.e. when we do not take the current coin

2) C(i,j)=C(i-1,j)

Now as both of them are independent and exhaustive , These both of these state makes up the total number of ways!!!

C(i,j)=C(i-1,j)+C(i-1,j-Denominations[i])

I will leave the recurrence when repetition allowed for you!

Upvotes: 1

Related Questions