 < Back to forum

### COINS - Bytelandian gold coins

uestion : http://www.spoj.com/problems/COINS/

My solution : https://ideone.com/oMl9qP

Asked by: Shivam_Singhal on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.

Preview

##### Enter your comment details below:

Preview

DP formula should be :
a[n]=max(n,func(n/2)+func(n/3)+func(n/4));

Shubham_Kumar_Gupta last updated on April 7, 2019, 6:34 p.m.

Why don't we check for the max of n/2 and func(n/2) and so on ?

Shivam_Singhal last updated on April 7, 2019, 6:34 p.m.

For a given value of n there can be only two possibilites :
1) n will give the maximum value .
2) exchange n into three coins : n/2, n/3 and n/4 and sum of these will give the maximum value.
these correspond to two states.

You can use :
a[n]=max(n,(max(n/2,fun(n/2))+max(n/3,fun(n/3))+max(n/4,fun(n/4))));
which basically reduces to:
a[n]=max(n,func(n/2)+func(n/3)+func(n/4));

Shubham_Kumar_Gupta last updated on April 7, 2019, 6:34 p.m.

Yes, the expanded form is what I have used. It's giving me WA.The only difference is that I have used memoisation.

Shivam_Singhal last updated on April 7, 2019, 6:34 p.m.

```you have used this:
a[n]=max(n,(max(n/2,a[n/2])+max(n/3,a[n/3])+max(n/4,a[n/4])));
the func function is called only once in the main function and never
in the function itself...therefore no recursion..
no memoization..no values stored in a (a will be empty).
ans this expression will simply evaluate to -
a[n]=max(n,(max(n/2,0)+max(n/3,0)+max(n/4,0)));
so func will return with just one call.

```
Shubham_Kumar_Gupta last updated on April 7, 2019, 6:34 p.m.

Found the error. I was supposed to call the function. Thank you.

Shivam_Singhal last updated on April 7, 2019, 6:34 p.m.

##### Instruction to write good question
1. 1. Write a title that summarizes the specific problem
2. 2. Pretend you're talking to a busy colleague
3. 3. Spelling, grammar and punctuation are important!