Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Java

Memoizing Fibonacci Numbers

Explore how to apply memoization to calculate Fibonacci numbers efficiently using dynamic programming in Java. Understand the reduction from exponential to linear time complexity by storing previously computed values to avoid redundant calculations, preparing you for coding interviews.

We'll cover the following...

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 calculations, 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.

Memoized code

Have a look at the complete code in Java:

Java
class Memoize
{ 
  public static int fib(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];
  }
  public static void main(String args[]) 
  {
    int n = 6; // Finding the nth Fibonacci number 
    int [] lookupTable = new int[n+1]; 
    for (int i = 0; i < n+1; i++)
      lookupTable[i] = -1; // Initializing the look up table to have -1
    System.out.println(fib(n, lookupTable));
  }
}

The function is very simple. It takes the following as input:

  • The ...