Hints for SPOJ COINS
Trying out COINS(Bytelandian Gold Coins) at spoj.pl ? not getting it? Try giving life to these cryptic ideas from my scratchpad -
while they speak of recursion, to speed up try memoization technique from dynamic programming.Labels: programming contest, recursion, SPOJ
posted by Abhishek Mishra @ Sunday, August 03, 2008
4 Comments
4 Comments:
what exactly do you mean by memorization in here?
see when you've got recursive solutions, on higher inputs the trace usually breaks to function calls on lower inputs and this becomes very repetitive for higher inputs. So, if you precalculate and store return values of the function for large number of small inputs, the faster your program works for those high inputs. as seen in this case. have a look at the analysis - Optimization by memorization
you ment memoization? http://en.wikipedia.org/wiki/Memoization
Woops!!! thanks for correcting me.. its memoization actually and not memorization
Post a Comment
Subscribe to Post Comments [Atom]
<< Home