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.
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));
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.
