Dynamic Programming in Go #1: Fibonacci
The requirement is to find Nth Fibonacci number.
Naive Method: Test
In this method, we have to attempt to remember the previous steps in order to not repeat future steps for a case that is already solved.
Suppose, Fn(5) = Fn(4) + Fn(3)
So in order to find Fn(5), we have to find Fn(4) and Fn(3).
Suppose we landed up in a situation in future where Fn(6) = Fn(5) + Fn(4).
So should we go ahead and calculate Fn(5) and Fn(4)?
Ideally no. Because we have already done that. So if we just remember the previous encounters somehow, we can utilise the results in future.
Memoized Method: Test
How can we measure the difference?
If we run the ‘Naive Method’ to find 35th Fibonacci, it takes ‘41077903’ nano seconds.
But if we run the ‘Memoized Method’ to find 100th Fibonacci, it takes ‘7539’ nano seconds.
So we are at a conclusion that the memoized method reduces considerably the processing time.
Folks, if you like my content, would you consider following me on linked in at: https://www.linkedin.com/in/hitesh-pattanayak-52290b160/