Fibonacci with Tabulation

Updated: 01 February 2024

Problem

Calculate the nth number in the Fibbonnaci sequence with:

  1. 0th number as 0
  2. 1st number as 1

So the resulting:

n:      0   1   2   3   4   5   6
fib(n)  0   1   1   2   3   5   8

The tabulation strategy consists of building a table but we think of the problem in terms of iteration instead of recursion

In this tabular representation something important to note is that for the value of n=6 we have an array with the indices 0 to 6 and a length of 7

Tabulation Implementation

For our implementation we will define a table that has a position for each value we want. For our starting seed we will define an array of 0s and a 1 at index 1, from here we will step through each item and add it to the following two items. This is a bit of a different perspective on the Fibonacci problem than in the Recursive Fibonacci example

dynamic-programming/tabulation/fib.ts
export const fib = (n: number): number => {
  const table = new Array(n + 1).fill(0);
  table[1] = 1;

  // A possible footgun here is increasing the size of the table
  // accidentially in the body and still refering to it in the for
  // condition, hence why we are referencing the input value of n instead
  for (let index = 0; index <= n; index++) {
    const element = table[index];

    const index1 = index + 1;
    if (index1 in table) table[index1] += element;

    const index2 = index + 2;
    if (index2 in table) table[index2] += element;
  }

  return table[n];
};

In this implementation we have a linear solution with time complexity $O(n)$ and space complexity of $O(n)$

An important thing to note about this solution is that it still represents a tree structure but is represented as a table: