Why Fibonacci Using DP in DSA Typescript?

The Big Idea

What if you could skip all repeated work and get Fibonacci numbers instantly?

The Scenario

Imagine you want to find the 40th number in the Fibonacci sequence by calculating each number one by one, starting from the beginning every time.

This means you keep repeating the same calculations over and over, like counting steps back and forth without remembering where you left off.

The Problem

This manual way is very slow because it repeats the same work many times.

It also wastes time and can make your program freeze or take too long to finish.

The Solution

Dynamic Programming (DP) helps by remembering the answers to smaller problems so you don't have to calculate them again.

It stores the Fibonacci numbers as it finds them, so each number is only calculated once.

Before vs After

✗ Before

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

✓ After

function fib(n: number): number {
  const dp: number[] = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

What It Enables

It makes finding big Fibonacci numbers fast and efficient, opening doors to solving many complex problems quickly.

Real Life Example

Calculating the number of ways to climb stairs when you can take one or two steps at a time is like Fibonacci with DP.

DP helps you find the answer quickly without trying every possible step combination.

Key Takeaways

Manual Fibonacci repeats work and is slow.

DP remembers past results to save time.

DP makes big calculations fast and practical.