Fibonacci with Tabulation
Updated: 01 February 2024
Problem
Calculate the nth number in the Fibbonnaci sequence with:
- 0th number as 0
- 1st number as 1
So the resulting:
1n: 0 1 2 3 4 5 62fib(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
1export 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 table6 // accidentially in the body and still refering to it in the for7 // condition, hence why we are referencing the input value of n instead8 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 and space complexity of
An important thing to note about this solution is that it still represents a tree structure but is represented as a table: