Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Memoizing Fibonacci Numbers

Explore how to apply memoization to Fibonacci number calculations in C++, reducing time complexity from exponential to linear. This lesson helps you understand the use of lookup tables in dynamic programming to avoid redundant computations, making recursive algorithms more efficient and practical for coding interviews.

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++,

C++
#include <iostream>
using namespace std;
int fib(const int n, int lookupTable[]) {
  if (lookupTable[n] == -1) { // Check if already present
    // Adding entry to table when not present
    if (n <= 1) 
      lookupTable[n] = n;
    else 
      lookupTable[n] = fib(n - 1, lookupTable) + fib(n - 2, lookupTable);
  }
  return lookupTable[n];
}
int main() {
  const int n = 6; // Finding the nth Fibonacci number 
  int lookupTable[n+1]; 
  for (int i = 0; i < n+1; i++)
    lookupTable[i] = -1; // Initializing the look up table to have -1
  cout << fib(n, lookupTable) << endl;
}

The function is very simple. ...