Code : E1-The white knight

general
,
1

Hi all!

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 :

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. :slight_smile:

Regards

2

basicly, with dynamic programming, you don’t compute the same value twice.

let’s have an example with fibonacci. i wanna know F(4).

doing it by recursion, you have to compute :

F(4) = F(3)               + F(2)
     = F(2)        + F(1) + F(1) + F(1)
     = F(1) + F(1) + F(1) + F(1) + F(1)
     = 5

in this one, for example, F(2) is computed twice (on the first line and on the second one).

doing it by dynamic programming, you compute :

F(2) = F(1) + F(1)
F(3) = F(2) + F(1)
F(4) = F(3) + F(2)

and every right value is a constant.

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.

hope this helps. :slight_smile:

2 Likes
3

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.

1 Like
4

Great! Thanks a lot cyberax and betlista. :slight_smile:
That really helped. Thank you. :slight_smile:

5

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.

6

It’s important to have a flag that you are counting something already to not to start counting again…