Fibonacci Using DP in DSA Javascript - Execution Trace

Concept Flow - Fibonacci Using DP

Start with n

↓

Create DP array of size n+1

↓

Initialize base cases: dp[0

↓

For i from 2 to n

↓

Calculate dp[i

↓

Return dp[n

We build a table from the bottom up, starting with known values, then fill each next value by adding the two before it until we reach n.

Execution Sample

DSA Javascript

function fibDP(n) {
  const dp = 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];
}

This code calculates the nth Fibonacci number using a bottom-up dynamic programming approach.

Execution Table

Step	Operation	Index i	dp Array State	Calculation	Result at dp[i]
1	Initialize dp array	-	[0, 0, 0, 0, 0, 0, 0]	-	-
2	Set base case dp[1]	1	[0, 1, 0, 0, 0, 0, 0]	-	-
3	Calculate dp[2]	2	[0, 1, 1, 0, 0, 0, 0]	dp[1] + dp[0] = 1 + 0	1
4	Calculate dp[3]	3	[0, 1, 1, 2, 0, 0, 0]	dp[2] + dp[1] = 1 + 1	2
5	Calculate dp[4]	4	[0, 1, 2, 2, 0, 0, 0]	dp[3] + dp[2] = 2 + 1	3
6	Calculate dp[5]	5	[0, 1, 2, 3, 0, 0, 0]	dp[4] + dp[3] = 3 + 2	5
7	Calculate dp[6]	6	[0, 1, 2, 3, 5, 0, 0]	dp[5] + dp[4] = 5 + 3	8
8	Return dp[n]	6	[0, 1, 2, 3, 5, 8, 0]	-	8

💡 Reached i = n (6), finished filling dp array, returned dp[6]

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
i	-	2	3	4	5	6	6
dp	[0,0,0,0,0,0,0]	[0,1,1,0,0,0,0]	[0,1,1,2,0,0,0]	[0,1,2,2,0,0,0]	[0,1,2,3,0,0,0]	[0,1,2,3,5,0,0]	[0,1,2,3,5,8,0]

Key Moments - 3 Insights

Why do we start filling dp array from index 2, not 0 or 1?

Because dp[0] and dp[1] are base cases already known (0 and 1). The loop starts at 2 to build from these known values, as shown in execution_table steps 3 onwards.

Why do we use dp[i-1] + dp[i-2] to fill dp[i]?

The Fibonacci number at position i is the sum of the two previous Fibonacci numbers. This is the core relation, clearly seen in the 'Calculation' column of the execution_table.

What happens if n is 0 or 1?

For n=0, dp[0] is 0 by initialization; for n=1, dp[1] is set to 1. The function returns these directly without entering the loop, as the loop starts from 2.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the value of dp[4]?

A 2

B 3

C 5

D 1

💡 Hint

Check the 'Result at dp[i]' column for Step 5 in the execution_table.

At which step does the dp array first contain the value 5?

A Step 6

B Step 4

C Step 5

D Step 7

💡 Hint

Look at the 'dp Array State' column and find when 5 appears first.

If we change the base case dp[1] to 2, what will be the value of dp[3] at Step 4?

A 3

B 5

C 4

D 2

💡 Hint

dp[3] = dp[2] + dp[1]. If dp[1] changes, recalculate dp[3] using the new dp[1].

Concept Snapshot

Fibonacci Using DP:
- Create array dp of size n+1
- Set dp[0]=0, dp[1]=1 as base cases
- For i=2 to n, dp[i] = dp[i-1] + dp[i-2]
- Return dp[n]
This avoids repeated calculations by storing results.

Full Transcript

This visualization shows how to calculate the Fibonacci number for n=6 using dynamic programming. We start by creating an array dp to store Fibonacci numbers from 0 to n. We set dp[0] to 0 and dp[1] to 1 as base cases. Then, for each index from 2 to n, we fill dp[i] by adding the two previous values dp[i-1] and dp[i-2]. The execution table tracks each step, showing the dp array's state and the calculation performed. The variable tracker shows how the index i and dp array change after each step. Key moments clarify why we start from index 2, why the sum of two previous dp values is used, and what happens for small n. The quiz tests understanding of dp array values at specific steps and effects of changing base cases. This method efficiently computes Fibonacci numbers by building from the bottom up and storing intermediate results.

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