Algorithms for Coding Interviews in Java/

...

/

Tabulating Fibonacci Numbers

Tabulating Fibonacci Numbers

Let's tabulate the code to find the nth Fibonacci number now.

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