Didn't understand the question

#1

Could you kindly explain how the 12 gets converted into 13 and how the coins are split?

#2

Hello @varun.saxena,

In this question you have consider three things:

  1. each coin has a number written on it.
  2. you can buy gold with a coin of amount(in kg) written on the coin.
  3. In exchange of your coin of value n, you can get three coins of values n/2, n/3, n/4 i.e. in total you would have a total amount of (int)(n/2) +(int)(n/3) +(int)(n/4)

Now, you have to calculate the max. amount(in kg) of gold you can buy, by the coin you are given initially.

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.

Hint:
From the problem definition, say a function, f (n) return ways to compute the change.

recursive statement/calls:
f (n) = max (n, f (n / 2) + f (n / 3) + f (n / 4)) // here recursion is taking place.
Base case:
f (0) = 0
f(1) =1

Hope, this would help.
if you still have doubts, feel free to ask.