So i’ve been working on this problem[ The white knight] and i first solved it using recursion which exceeded the time limit. So later i found out that their was a tutorial about this problem here : http://www.codechef.com/wiki/tutorial-white-knight
However, what i dont understand is how does this approach i.e : dynamic programming, beat recursion in terms of time. Shouldnt it be the same?
I even tried memoization with recursion, but even that exceeded the time limit. Some help needed. And will be greatly appreciated.
in the recursion algorithm, the complexity is exponential.
in the dp algorithm, the complexity is linear.
that’s why the execution time is different. the bigger N is, the bigger the difference between both is.
using memoization in the recursion algorithm makes the time complexity become linear (as each value is kept in memory to be used further), but the space complexity is bad (as you have to remember all the values). in dp, you can just keep the last two values, only them are necessary to compute the next term.
One small note to this perfect answer - if you would like to use recursion for F(10.000) you will get StackOverflowError - you won’t have enough memory for deep recursion.
Even i was facing the same problem and landed up here…
the above comment by cyberax and betlista answers the difference between dp and recursion very well but i have a question … can excessive space requirement lead to time limit exceeded won’t it lead to run time error.
Does referencing a memory location directly in memoization takes so much of time??
Any suggestions or comments will be highly appreciated.