Fibonacci Using DP in DSA Typescript - Build from Scratch

Fibonacci Using DP

📖 Scenario: You are helping a friend who wants to find the nth number in the Fibonacci sequence quickly. The Fibonacci sequence starts with 0 and 1, and each next number is the sum of the two before it.Calculating Fibonacci numbers by repeating the same work can be slow. So, you will use a method called Dynamic Programming (DP) to remember past results and speed things up.

🎯 Goal: Build a TypeScript program that uses Dynamic Programming to find the nth Fibonacci number efficiently.

📋 What You'll Learn

Create an array to store Fibonacci numbers up to n.

Use a loop to fill the array with Fibonacci numbers.

Use Dynamic Programming to avoid repeated calculations.

Print the nth Fibonacci number.

💡 Why This Matters

🌍 Real World

Calculating Fibonacci numbers quickly is useful in computer science problems, financial models, and nature simulations where repeated calculations can slow down programs.

💼 Career

Understanding Dynamic Programming and efficient algorithms is important for software development, especially in roles involving optimization and problem solving.

1

Create the input variable n

Create a variable called n and set it to 10 to represent the position in the Fibonacci sequence you want to find.

DSA Typescript

# Your code here
// Create a variable called n and set it to 10

Hint

Use const n = 10; to create the variable.

2

Create the array fib to store Fibonacci numbers

Create an array called fib with size n + 1. Initialize fib[0] to 0 and fib[1] to 1.

DSA Typescript

const n = 10;
// Create an array fib with size n + 1
// Initialize fib[0] = 0 and fib[1] = 1
// Your code here

Hint

Use new Array(n + 1) to create the array and assign the first two Fibonacci numbers.

3

Fill the fib array using a loop and Dynamic Programming

Use a for loop with variable i starting from 2 up to n. Inside the loop, set fib[i] to fib[i - 1] + fib[i - 2].

DSA Typescript

const n = 10;
const fib: number[] = new Array(n + 1);
fib[0] = 0;
fib[1] = 1;
// Use a for loop from i = 2 to n
// Calculate fib[i] = fib[i - 1] + fib[i - 2]
// Your code here

Hint

Use a for loop and update fib[i] inside it.

4

Print the nth Fibonacci number

Write a console.log statement to print the value of fib[n].

DSA Typescript

const n = 10;
const fib: number[] = new Array(n + 1);
fib[0] = 0;
fib[1] = 1;
for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
}
// Print fib[n] below
// Your code here

Hint

Use console.log(fib[n]); to print the result.