# 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: