Exchanging coins DP

#1

Not getting logic of the problem and recursion tree of the problem

#2

hi @kumarakash121005,

From the problem definition, say f (n) = ways to compute the change.

  • f (n) = max (n, f (n / 2) + f (n / 3) + f (n / 4)) (by definition).
  • f (0) = 0 (Base case)

Suppose, N=12
now you have two choices:

  1. do not exchange coin with bank, i.e total amount=12
  2. exchange n to (n/2,n/3,n/4) i.e. total amount=6+4+3=13

Now, you have to select max of both. here it is 13.
Recursively, you can break the coins further and than return the max of above two choices/amounts.
But, the parameter we are passing every time in function is an integer, so some values of n will repeat.

This satisfies two conditions of DP i.e. Optimal substructure and overlapping substructures.

In our case, the max. value of will come out to be 13.

you can look here implementation difficulties https://ide.codingblocks.com/s/659405