Memoizing Fibonacci Numbers

In the last lesson, we introduced the basic concept of dynamic programming and its two patterns: memoization and tabulation.

In the first lesson of this chapter, 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++,