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.

Practice

1. What is the main advantage of using Dynamic Programming (DP) to calculate Fibonacci numbers compared to a simple recursive approach?

easy

A. It uses less memory by not storing any results.

B. It avoids repeated calculations by storing intermediate results.

C. It calculates Fibonacci numbers randomly.

D. It only works for small Fibonacci numbers.

Solution

1. Step 1: Understand recursive Fibonacci calculation

   Simple recursion recalculates the same Fibonacci numbers many times, causing inefficiency.

2. Step 2: Understand DP optimization

   DP stores previously calculated Fibonacci numbers in a table (memoization or tabulation) to avoid repeated work.

3. Final Answer:

   It avoids repeated calculations by storing intermediate results. -> Option B

4. Quick Check:

   DP = stores results to save time [OK]

Hint: DP saves time by remembering past answers [OK]

Common Mistakes:

• Thinking DP uses less memory than recursion
• Believing DP calculates randomly
• Assuming DP only works for small inputs

2. Which of the following TypeScript code snippets correctly initializes the DP array for Fibonacci calculation up to n?

easy

A. const dp: number[] = new Array(n + 1).fill(0); dp[1] = 1;

B. const dp: number[] = new Array(n).fill(1);

C. const dp: number[] = []; dp[0] = 1; dp[1] = 1;

D. const dp: number[] = new Array(n + 1); dp[1] = 1;

Solution

1. Step 1: Check array size and initialization

   We need an array of size n+1 to store Fibonacci numbers from 0 to n. Filling with 0 and setting dp[1] = 1 is correct.

2. Step 2: Validate each option

   const dp: number[] = new Array(n + 1).fill(0); dp[1] = 1; correctly creates dp with size n+1, fills with 0, and sets dp[1] = 1. Others have wrong sizes or initial values.

3. Final Answer:

   const dp: number[] = new Array(n + 1).fill(0); dp[1] = 1; -> Option A

4. Quick Check:

   Array size = n+1, dp[1] = 1 [OK]

Hint: DP array size must be n+1 with dp[1] = 1 [OK]

Common Mistakes:

• Using array size n instead of n+1
• Initializing dp[0] or dp[1] incorrectly
• Leaving dp array uninitialized

3. What will be the output of the following TypeScript code?

function fib(n: number): number {
  const dp: number[] = new Array(n + 1).fill(0);
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
console.log(fib(5));

medium

A. 13

B. 8

C. 3

D. 5

Solution

1. Step 1: Trace DP array values for n=5

   dp[0]=0, dp[1]=1; then dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5.

2. Step 2: Return dp[5]

   The function returns dp[5] which is 5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Remember Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing index starting point
• Returning dp[n-1] instead of dp[n]
• Miscomputing dp values in loop

4. Identify the error in this TypeScript DP Fibonacci code and select the fix:

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

medium

A. Change array size to n+1.

B. Initialize dp[2] to 1 before the loop.

C. Start loop from i = 1 instead of 2.

D. Remove dp[0] initialization.

Solution

1. Step 1: Analyze array size and access

   Array dp has size n, but loop accesses dp[n] beyond the initial length.

2. Step 2: Fix array size

   Increase dp size to n+1 to safely access dp[n].

3. Final Answer:

   Change array size to n+1 to avoid out-of-bounds error. -> Option A

4. Quick Check:

   Array size must cover dp[n] [OK]

Hint: Array size must be n+1 for dp[n] access [OK]

Common Mistakes:

• Ignoring array size mismatch
• Starting loop incorrectly
• Unnecessary dp initialization changes

5. You want to optimize the space used by the DP Fibonacci function. Which modification correctly reduces space complexity from O(n) to O(1)?

hard

A. Use a recursive function without memoization.

B. Store all Fibonacci numbers in a global array.

C. Use two variables to store only the last two Fibonacci numbers instead of an array.

D. Initialize the dp array with zeros and fill it completely every call.

Solution

1. Step 1: Understand space usage in DP Fibonacci

   DP uses an array of size n+1, so space is O(n).

2. Step 2: Optimize space by storing only needed values

   Since each Fibonacci number depends only on the previous two, storing just two variables suffices.

3. Step 3: Compare options

   Use two variables to store only the last two Fibonacci numbers instead of an array. uses two variables, reducing space to O(1). Others do not reduce space or are inefficient.

4. Final Answer:

   Use two variables to store only the last two Fibonacci numbers instead of an array. -> Option C

5. Quick Check:

   Two vars = O(1) space [OK]

Hint: Keep only last two Fibonacci numbers to save space [OK]

Common Mistakes:

• Using recursion without memoization increases time
• Storing all numbers globally wastes space
• Filling full dp array every call wastes memory