Tabulation Bottom Up DP in DSA Typescript - Build from Scratch

Tabulation Bottom Up DP: Fibonacci Sequence

📖 Scenario: Imagine you want to find the nth number in the Fibonacci sequence. This sequence starts with 0 and 1, and each next number is the sum of the two before it.Using a smart way called Tabulation Bottom Up Dynamic Programming, you will build the sequence step by step from the bottom up, saving results to avoid repeating work.

🎯 Goal: Build a TypeScript program that uses tabulation to find the Fibonacci number at position n. You will create a table (array) to store results and fill it from the start up to n.

📋 What You'll Learn

Create an array called fibTable with size n + 1 to store Fibonacci numbers

Set the first two Fibonacci numbers in fibTable as 0 and 1

Use a for loop with variable i from 2 to n to fill fibTable

Calculate each Fibonacci number as the sum of the two previous numbers in fibTable

Print the Fibonacci number at position n from fibTable

💡 Why This Matters

🌍 Real World

Tabulation bottom up dynamic programming is used in many real-world problems like calculating sequences, optimizing resource allocation, and solving complex puzzles efficiently.

💼 Career

Understanding tabulation helps in software engineering roles that require optimization and efficient algorithm design, such as game development, data analysis, and system design.

1

Create the Fibonacci table array

Create a variable called n and set it to 7. Then create an array called fibTable with size n + 1 filled with zeros.

DSA Typescript

const n = 7;
// Your code here

Hint

Use new Array(n + 1).fill(0) to create an array of zeros with length n + 1.

2

Initialize the first two Fibonacci numbers

Set fibTable[0] to 0 and fibTable[1] to 1.

DSA Typescript

const n = 7;
const fibTable: number[] = new Array(n + 1).fill(0);
// Your code here

Hint

Assign the first two Fibonacci numbers directly to the first two positions of the array.

3

Fill the Fibonacci table using a for loop

Use a for loop with variable i from 2 to n inclusive. Inside the loop, set fibTable[i] to the sum of fibTable[i - 1] and fibTable[i - 2].

DSA Typescript

const n = 7;
const fibTable: number[] = new Array(n + 1).fill(0);
fibTable[0] = 0;
fibTable[1] = 1;
// Your code here

Hint

Loop from 2 to n and fill each position by adding the two previous values in the array.

4

Print the Fibonacci number at position n

Print the value of fibTable[n] using console.log.

DSA Typescript

const n = 7;
const fibTable: number[] = new Array(n + 1).fill(0);
fibTable[0] = 0;
fibTable[1] = 1;
for (let i = 2; i <= n; i++) {
    fibTable[i] = fibTable[i - 1] + fibTable[i - 2];
}
// Your code here

Hint

Use console.log(fibTable[n]) to print the final Fibonacci number.