Showing wrong error in my code what is the problem and how should i approach

#1
#2

hi @mohit26900,
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

#3

But why we are calculating sub problems

#4

@mohit26900 bcoz u can again exchange the coins, here it says exchange as many times as you need to maximise

#5

int dp[n+1]; dp[0]=0; for(int i=1;i<n+1;i++) { dp[i]=max(i,dp[i/2]+dp[i/3]+dp[i/4]); } cout<<dp[n];

#6

doing with top down showing TLE

#7

https://ide.codingblocks.com/s/660161. showing TLE

#8

@mohit26900, top down passes all test case the one I gave, have u checked?

#9

which one you gave to me?

#10

@mohit26900 https://ide.codingblocks.com/s/659405

#11

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.