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:

1
n:      0   1   2   3   4   5   6
2
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
1
export const fib = (n: number): number => {
2
  const table = new Array(n + 1).fill(0);
3
  table[1] = 1;
4


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


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


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


18
  return table[n];
19
};

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

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