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.