Fibonacci Using DP in DSA Javascript

Mental Model

Remember past Fibonacci numbers so you don't calculate them again.

Analogy: Like writing down answers on a notebook so you don't solve the same math problem 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 the 5th Fibonacci number 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 step to get the 5th Fibonacci number

Result:

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

Annotated Code

DSA Javascript

class FibonacciDP {
  constructor() {
    this.fib = [];
  }

  calculate(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;

    this.fib[0] = 0; // base case
    this.fib[1] = 1; // base case

    for (let i = 2; i <= n; i++) {
      this.fib[i] = this.fib[i - 1] + this.fib[i - 2]; // build fib[i] from previous two
    }

    return this.fib[n]; // return nth Fibonacci number
  }
}

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

if (n === 0) return 0;

handle base case n=0

if (n === 1) return 1;

handle base case n=1

this.fib[0] = 0; // base case

initialize fib[0]

this.fib[1] = 1; // base case

initialize fib[1]

for (let i = 2; i <= n; i++) {

loop from 2 to n to fill fib array

this.fib[i] = this.fib[i - 1] + this.fib[i - 2];

calculate fib[i] using previous two values

return this.fib[n];

return the nth Fibonacci number

Output

Fibonacci number for n=5 is 5

Complexity Analysis

Time: O(n) because we calculate 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 Javascript

if (n === 0) return 0;

n = 1

Returns 1 immediately as base case

DSA Javascript

if (n === 1) return 1;

large n (e.g., 50)

Calculates efficiently without repeated work, but uses more memory

DSA Javascript

for (let i = 2; i <= n; i++) {

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 an array to store computed Fibonacci numbers and build up from base cases

Summary

Calculates Fibonacci numbers efficiently by remembering past results.

Use when you need Fibonacci numbers or similar sequences without slow repeated calculations.

The key is to build the answer step-by-step using stored smaller answers.

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 calculates Fibonacci numbers using only recursion without loops

C. It stores intermediate results to avoid repeated calculations

D. It always returns the Fibonacci sequence in reverse order

Solution

1. Step 1: Understand recursion vs DP

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

2. Step 2: Role of DP in Fibonacci

   DP stores previously calculated Fibonacci values in a table (memoization or tabulation) to reuse them, avoiding repeated work.

3. Final Answer:

   It stores intermediate results to avoid repeated calculations -> Option C

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 does not use loops or arrays
• Confusing DP with simple recursion

2. Which of the following JavaScript code snippets correctly initializes an array for bottom-up DP to compute Fibonacci numbers up to n?

easy

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

B. const fib = []; fib[0] = 1; fib[1] = 1;

C. const fib = new Array(n).fill(0); fib[1] = 1;

D. const fib = new Array(n+1).fill(1); fib[0] = 0;

Solution

1. Step 1: Array size for DP

   We need an array of size n+1 to store Fibonacci numbers from 0 to n.

2. Step 2: Initial values for Fibonacci

   Fibonacci sequence starts with fib[0] = 0 and fib[1] = 1, so these must be set correctly.

3. Final Answer:

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

4. Quick Check:

   Array size n+1, fib[0]=0, fib[1]=1 [OK]

Hint: Array size n+1 with fib[0]=0 and fib[1]=1 [OK]

Common Mistakes:

• Using array size n instead of n+1
• Setting fib[0] = 1 incorrectly
• Filling array with 1 instead of 0

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

function fibDP(n) {
  const fib = [0, 1];
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  return fib[n];
}
console.log(fibDP(6));

medium

A. 8

B. 13

C. 21

D. 34

Solution

1. Step 1: Trace Fibonacci values up to n=6

   fib[0]=0, fib[1]=1, fib[2]=1, fib[3]=2, fib[4]=3, fib[5]=5, fib[6]=8.

2. Step 2: Return fib[6]

   The function returns fib[6], which is 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   fib(6) = 8 [OK]

Hint: fib(6) = 8 by adding previous two numbers [OK]

Common Mistakes:

• Confusing index and value (e.g., fib[6] = 13)
• Starting array with wrong initial values
• Off-by-one errors in loop

4. Identify the error in this JavaScript DP Fibonacci function and choose the correct fix:

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

medium

A. Remove the loop and use recursion instead

B. Initialize fib array with zeros instead of [0,1]

C. Change return to fib[n-1] to fix off-by-one

D. Change loop start to i = 2 to avoid undefined fib[-1]

Solution

1. Step 1: Analyze loop start index

   The loop starts at i=1, so fib[i-2] becomes fib[-1] which is undefined and causes error.

2. Step 2: Correct loop start

   Starting loop at i=2 ensures fib[i-2] is fib[0], which is defined, fixing the error.

3. Final Answer:

   Change loop start to i = 2 to avoid undefined fib[-1] -> Option D

4. Quick Check:

   Loop from 2 avoids negative index [OK]

Hint: Start loop at 2 to avoid negative indices [OK]

Common Mistakes:

• Starting loop at 1 causing undefined access
• Changing return index incorrectly
• Removing DP and using recursion unnecessarily

5. Given the following code to compute Fibonacci numbers using DP, what will be the output of fibDP(0) and fibDP(1)? How does the function handle these edge cases?

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

hard

A. fibDP(0) = 1, fibDP(1) = 1; initializes fib array incorrectly

B. fibDP(0) = 0, fibDP(1) = 1; returns n directly for n ≤ 1

C. fibDP(0) = 0, fibDP(1) = 0; misses setting fib[1] properly

D. fibDP(0) and fibDP(1) cause errors due to array size

Solution

1. Step 1: Check base case handling

   The function returns n directly if n ≤ 1, so fibDP(0) returns 0 and fibDP(1) returns 1 immediately.

2. Step 2: Confirm array initialization and loop

   For n > 1, the array is initialized and filled correctly, but for n=0 or 1, the function returns early, handling edge cases properly.

3. Final Answer:

   fibDP(0) = 0, fibDP(1) = 1; returns n directly for n ≤ 1 -> Option B

4. Quick Check:

   Edge cases return n directly [OK]

Hint: Returns n directly for n ≤ 1 to handle edges [OK]

Common Mistakes:

• Not handling n=0 or n=1 separately
• Incorrect array initialization for small n
• Assuming loop runs for n=0 or n=1