Fibonacci Using DP in DSA Typescript - Execution Trace

Concept Flow - Fibonacci Using DP

Start

↓

Initialize DP array with base cases: dp[0

↓

For i from 2 to n

↓

Calculate dp[i

↓

Store dp[i

↓

Repeat until i == n

↓

Return dp[n

↓

End

This flow shows how we build the Fibonacci sequence step-by-step using a DP array, starting from base cases and filling up to n.

Execution Sample

DSA Typescript

function fibonacciDP(n: number): number {
  const dp = [0, 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 DP approach, storing intermediate results in an array.

Execution Table

Step	Operation	Index i	dp Array State	Calculation	Result Stored
1	Initialize base cases	-	[0, 1]	-	-
2	Calculate dp[2]	2	[0, 1, -]	dp[1] + dp[0] = 1 + 0	1
3	Calculate dp[3]	3	[0, 1, 1, -]	dp[2] + dp[1] = 1 + 1	2
4	Calculate dp[4]	4	[0, 1, 1, 2, -]	dp[3] + dp[2] = 2 + 1	3
5	Calculate dp[5]	5	[0, 1, 1, 2, 3, -]	dp[4] + dp[3] = 3 + 2	5
6	Calculate dp[6]	6	[0, 1, 1, 2, 3, 5, -]	dp[5] + dp[4] = 5 + 3	8
7	Calculate dp[7]	7	[0, 1, 1, 2, 3, 5, 8, -]	dp[6] + dp[5] = 8 + 5	13
8	Calculate dp[8]	8	[0, 1, 1, 2, 3, 5, 8, 13, -]	dp[7] + dp[6] = 13 + 8	21
9	Calculate dp[9]	9	[0, 1, 1, 2, 3, 5, 8, 13, 21, -]	dp[8] + dp[7] = 21 + 13	34
10	Calculate dp[10]	10	[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, -]	dp[9] + dp[8] = 34 + 21	55
11	Return dp[10]	10	[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]	-	55

💡 Loop ends when i exceeds n (10), dp array fully computed up to dp[10]

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	Final
i	-	2	3	4	5	6	7	8	9	10	11 (exit)
dp	[0,1]	[0,1,1]	[0,1,1,2]	[0,1,1,2,3]	[0,1,1,2,3,5]	[0,1,1,2,3,5,8]	[0,1,1,2,3,5,8,13]	[0,1,1,2,3,5,8,13,21]	[0,1,1,2,3,5,8,13,21,34]	[0,1,1,2,3,5,8,13,21,34,55]	[0,1,1,2,3,5,8,13,21,34,55]

Key Moments - 3 Insights

Why do we start the loop from i=2 and not from 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 rows 2 and onward.

What happens if we try to access dp[i-1] or dp[i-2] before they are computed?

This does not happen because the loop fills dp in order from 2 upwards, ensuring dp[i-1] and dp[i-2] are always computed before dp[i], as seen in the dp array states in execution_table.

Why do we store all Fibonacci numbers up to n instead of just calculating the nth directly?

Storing all intermediate results avoids repeated calculations and makes the algorithm efficient. This is the core idea of dynamic programming, demonstrated by the dp array growing step-by-step in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the dp array state?

A [0, 1, 1, 2, 3]

B [0, 1, 1, 2, 3, 5]

C [0, 1, 1, 2, 3, -]

D [0, 1, 1, 2, 3, 5, 8]

💡 Hint

Check the 'dp Array State' column in execution_table row 5.

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

A Step 7

B Step 6

C Step 8

D Step 9

💡 Hint

Look at the 'Result Stored' and 'dp Array State' columns in execution_table rows 6 to 8.

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

A 2

B 4

C 3

D 5

💡 Hint

dp[3] = dp[2] + dp[1]. Changing dp[1] affects dp[3]. Check execution_table Step 3 calculation.

Concept Snapshot

Fibonacci Using DP:
- Use an array dp to store Fibonacci numbers.
- Initialize dp[0]=0, dp[1]=1.
- For i from 2 to n, dp[i] = dp[i-1] + dp[i-2].
- Return dp[n] as the result.
- Avoids repeated calculations by storing intermediate results.

Full Transcript

This visualization shows how to calculate Fibonacci numbers using dynamic programming. We start with base cases dp[0]=0 and dp[1]=1. Then, for each index i from 2 to n, we calculate dp[i] by adding the two previous Fibonacci numbers dp[i-1] and dp[i-2]. We store each result in the dp array. This process continues until we reach dp[n], which is returned as the final Fibonacci number. The execution table tracks each step, showing the dp array growing and the calculations performed. The variable tracker shows how the loop index i and dp array change after each iteration. Key moments clarify why the loop starts at 2, why previous dp values are always available, and why storing intermediate results is important. The quiz tests understanding of dp array states and the effect of changing base cases. This method efficiently computes Fibonacci numbers by avoiding repeated work.

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