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

Tabulating Fibonacci Numbers

Explore how to calculate Fibonacci numbers using dynamic programming and tabulation in Java. Understand how to implement bottom-up iterative solutions that improve performance by using constant space and linear time, enhancing your coding interview skills in algorithm optimization.

We'll cover the following...

Now, let’s find the nthnth Fibonacci number using bottom-up tabulation. This approach uses iteration and can essentially be thought of as recursion in reverse.

Tabulated version #1

Have a look at the tabulated code in Java:

Java
class Tabulation
{ 
  public static int fib(int n, int[] lookupTable) 
  { 
    lookupTable[0] = 0; // Set zeroth and first values
    lookupTable[1] = 1;
    
    for (int i = 2; i <= n; i++) 
        lookupTable[i] = lookupTable[i-1] + lookupTable[i-2]; // Fill up the table by summing up previous two values
    
    return lookupTable[n]; // Return the nth Fibonacci number
  } 
  public static void main(String args[]) {
    int n = 6;
    int[] lookupTable = new int[n+1];
    System.out.print(fib(n, lookupTable));
  }
}

This algorithm:

  • Initializes a lookup table and sets the values of fib(0) and fib(1), as those are the base cases on lines 5-6.
  • Finds out the
...