Memoizing Fibonacci Numbers

In this lesson, we are going to reduce the time complexity of the Fibonacci code we wrote using a dynamic programming technique called memoization

We'll cover the following

In Calculating Fibonnacci Numbers, we established that the recursive implementation of the Fibonacci sequence causes recalculations which result in exponential time complexity.

Let’s memoize the code now and see where that leads us. The basic idea is to check if an array already contains the result of the Fibonacci number that we are trying to find before calculating it.

Pseudocode

IF the value at `n` is not present in the table:
 set the value of the lookup table at that index to `n` if `n` is less than or equal to 1. 
 OTHERWISE, set the value of the lookup table at that index to the sum of fib(n-1, table) and fib(n-2, table)
ELSE:
 return the value in the table by indexing

Memoized code

Have a look at the complete code in C++,

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.