Fibonacci Using DP in DSA Typescript

Mental Model

Remember past Fibonacci numbers so you don't repeat work. This saves time by reusing answers.

Analogy: Like writing down answers on a notepad while solving a puzzle, so you don't solve the same part twice.

fib[0] = 0
fib[1] = 1
fib[2] = ?
fib[3] = ?
fib[4] = ?
...

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using DP

Goal: Find fib(5) efficiently by storing previous results

Step 1: Initialize fib array with fib[0]=0 and fib[1]=1

fib = [0, 1, ?, ?, ?, ?]

Why: Base cases are known and needed to build next numbers

Step 2: Calculate fib[2] = fib[1] + fib[0] = 1 + 0

fib = [0, 1, 1, ?, ?, ?]

Why: Use stored values to find next Fibonacci number

Step 3: Calculate fib[3] = fib[2] + fib[1] = 1 + 1

fib = [0, 1, 1, 2, ?, ?]

Why: Build next number using previous two

Step 4: Calculate fib[4] = fib[3] + fib[2] = 2 + 1

fib = [0, 1, 1, 2, 3, ?]

Why: Continue building sequence

Step 5: Calculate fib[5] = fib[4] + fib[3] = 3 + 2

fib = [0, 1, 1, 2, 3, 5]

Why: Final answer for fib(5)

Result:

fib = [0, 1, 1, 2, 3, 5]
Answer: 5

Annotated Code

DSA Typescript

class FibonacciDP {
  static fib(n: number): number {
    if (n <= 1) return n;
    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];
    }
    return fib[n];
  }
}

const n = 5;
const result = FibonacciDP.fib(n);
console.log(`Fibonacci number for n=${n} is ${result}`);

if (n <= 1) return n;

handle base cases directly

fib[0] = 0; fib[1] = 1;

initialize first two Fibonacci numbers

for (let i = 2; i <= n; i++) { fib[i] = fib[i - 1] + fib[i - 2]; }

build Fibonacci numbers from bottom up using stored results

return fib[n];

return the final computed Fibonacci number

Output

Fibonacci number for n=5 is 5

Complexity Analysis

Time: O(n) because we compute each Fibonacci number once from 2 to n

Space: O(n) because we store all Fibonacci numbers up to n in an array

vs Alternative: Compared to naive recursion which is O(2^n), DP is much faster by avoiding repeated calculations

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Typescript

if (n <= 1) return n;

n = 1

Returns 1 immediately as base case

DSA Typescript

if (n <= 1) return n;

large n (e.g., 50)

Computes efficiently without stack overflow or repeated work

DSA Typescript

for (let i = 2; i <= n; i++) { fib[i] = fib[i - 1] + fib[i - 2]; }

When to Use This Pattern

When you see a problem asking for Fibonacci or similar sequences, use DP to store past results and avoid repeated work.

Common Mistakes

Mistake: Using naive recursion without memoization causing exponential time
Fix: Use a loop with an array to store computed Fibonacci numbers

Mistake: Not handling base cases n=0 or n=1 correctly
Fix: Add a condition to return n directly if n <= 1

Summary

Calculates Fibonacci numbers efficiently by storing previous results.

Use when you need Fibonacci numbers or similar sequences to avoid repeated calculations.

Remember to build from the bottom up and save answers to reuse.