Fibonacci Using DP in DSA C# - Execution Trace

Concept Flow - Fibonacci Using DP

Start with n

↓

Create DP array of size n+1

↓

Set 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 using the sum of the two before it.

Execution Sample

DSA C#

int FibonacciDP(int n) {
  int[] dp = new int[n + 1];
  dp[0] = 0;
  if (n >= 1) dp[1] = 1;
  for (int 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	i	dp Array State	Calculation	Result at dp[i]
1	Initialize dp array	-	[0, 0, 0, 0, 0, 0]	-	-
2	Set base cases	-	[0, 1, 0, 0, 0, 0]	-	-
3	Calculate dp[2]	2	[0, 1, 1, 0, 0, 0]	dp[1] + dp[0] = 1 + 0	1
4	Calculate dp[3]	3	[0, 1, 1, 2, 0, 0]	dp[2] + dp[1] = 1 + 1	2
5	Calculate dp[4]	4	[0, 1, 1, 2, 3, 0]	dp[3] + dp[2] = 2 + 1	3
6	Calculate dp[5]	5	[0, 1, 1, 2, 3, 5]	dp[4] + dp[3] = 3 + 2	5
7	Return result	-	-	-	5

💡 Loop ends when i > n (i=6 > 5), dp[5] holds the Fibonacci number for n=5

Variable Tracker

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

Key Moments - 3 Insights

Why do we set dp[0] = 0 and dp[1] = 1 before the loop?

Because these are the base Fibonacci numbers. The loop uses these to calculate all other values. See execution_table rows 2 and 3 where dp[2] depends on dp[1] and dp[0].

Why does the loop start from i=2 instead of i=0 or i=1?

Because dp[0] and dp[1] are already known and set. Starting at 2 means we build from these base cases. Refer to execution_table row 3 where calculation begins at i=2.

How does dp[i] get its value inside the loop?

Each dp[i] is the sum of the two previous Fibonacci numbers dp[i-1] and dp[i-2]. This is shown in the 'Calculation' column of the execution_table rows 3 to 6.

Visual Quiz - 3 Questions

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

A 3

B 2

C 5

D 1

💡 Hint

Check the 'dp Array State' and 'Result at dp[i]' columns in row 5 of the execution_table.

At which step does the loop finish calculating the Fibonacci number for n=5?

A Step 4

B Step 7

C Step 6

D Step 5

💡 Hint

Look at the 'i' column and the 'Operation' column in the execution_table to see when i reaches 5.

If we change dp[0] to 1, how would dp[2] change at step 3?

A dp[2] would be 0

B dp[2] would be 2

C dp[2] would be 1

D dp[2] would be 3

💡 Hint

dp[2] = dp[1] + dp[0], so changing dp[0] affects dp[2]. Check calculation in step 3.

Concept Snapshot

Fibonacci Using DP:
- Create dp array size n+1
- Set dp[0]=0, dp[1]=1 (base cases)
- For i=2 to n: dp[i]=dp[i-1]+dp[i-2]
- Return dp[n]
- Efficient: avoids repeated calculations
- Time: O(n), Space: O(n)

Full Transcript

This visualization shows how to calculate the Fibonacci number for a given n using dynamic programming. We start by creating an array dp to store Fibonacci numbers from 0 to n. We set the first two values dp[0] = 0 and dp[1] = 1 as base cases. Then, starting from i=2, we fill dp[i] by adding the two previous values dp[i-1] and dp[i-2]. This process continues until we reach dp[n], which is the Fibonacci number we want. The execution table tracks each step, showing how the dp array changes and how each dp[i] is calculated. The variable tracker shows how the loop variable i and the dp array evolve. Key moments clarify why base cases are set and why the loop starts at 2. The quiz tests understanding of dp array values and loop behavior. This method is efficient because it calculates each Fibonacci number once and stores it, avoiding repeated work.

Practice

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

easy

A. It calculates Fibonacci numbers randomly

B. It uses less memory by not storing any results

C. It stores intermediate results to avoid repeated calculations

D. It only works for small Fibonacci numbers

Solution

1. Step 1: Understand recursion inefficiency

   Simple recursion recalculates the same Fibonacci numbers many times, causing exponential time complexity.

2. Step 2: Role of Dynamic Programming

   DP stores previously calculated Fibonacci numbers in a table (memoization or tabulation), so each number is computed once.

3. Final Answer:

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

4. Quick Check:

   DP avoids repeated work = C [OK]

Hint: DP saves results to prevent repeated work [OK]

Common Mistakes:

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

2. Which of the following C# code snippets correctly initializes the DP array for Fibonacci calculation of size n?

easy

A. int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1;

B. int[] dp = new int[n]; dp[0] = 1; dp[1] = 1;

C. int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 0;

D. int[] dp = new int[n]; dp[0] = 0; dp[1] = 1;

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 dp[0] = 0 and dp[1] = 1.

3. Final Answer:

   int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; -> Option A

4. Quick Check:

   Correct size and base values = A [OK]

Hint: DP array size = n+1, start with 0 and 1 [OK]

Common Mistakes:

• Using array size n instead of n+1
• Swapping dp[0] and dp[1] values
• Starting dp[0] or dp[1] with wrong numbers

3. What is the output of the following C# code snippet?

int n = 5;
int[] dp = new int[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}
Console.WriteLine(dp[n]);

medium

A. 13

B. 8

C. 3

D. 5

Solution

1. Step 1: Calculate Fibonacci values up to n=5

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

2. Step 2: Output dp[5]

   The code prints dp[5], which is 5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Fibonacci(5) = 5 by adding previous two numbers [OK]

Common Mistakes:

• Confusing Fibonacci index starting at 0 or 1
• Calculating dp[5] as 8 or 13 incorrectly
• Off-by-one errors in loop

4. Identify the error in this C# code for Fibonacci using DP:

int n = 6;
int[] dp = new int[n];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}
Console.WriteLine(dp[n]);

medium

A. Array size is too small causing IndexOutOfRangeException

B. dp[0] and dp[1] are initialized incorrectly

C. Loop condition should be i < n instead of i <= n

D. No error, code runs fine

Solution

1. Step 1: Check array size and indexing

   Array dp has size n=6, valid indices 0 to 5. Loop runs i=2 to 6 inclusive, accessing dp[6] which is out of bounds.

2. Step 2: Resulting error

   Accessing dp[6] causes IndexOutOfRangeException at runtime.

3. Final Answer:

   Array size is too small causing IndexOutOfRangeException -> Option A

4. Quick Check:

   Array size < loop max index = error [OK]

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

Common Mistakes:

• Using array size n instead of n+1
• Ignoring loop boundary causing runtime error
• Assuming code runs without error

5. You want to find the 10th Fibonacci number using bottom-up DP but only want to use O(1) space instead of an array. Which approach below correctly implements this optimization?

hard

A. int[] dp = new int[10]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= 10; i++) dp[i] = dp[i - 1] + dp[i - 2]; Console.WriteLine(dp[10]);

B. int a = 0, b = 1, c = 0; for (int i = 2; i <= 10; i++) { c = a + b; a = b; b = c; } Console.WriteLine(c);

C. int a = 0, b = 1; for (int i = 2; i < 10; i++) { a = a + b; b = a; } Console.WriteLine(b);

D. int fib = 0; for (int i = 0; i <= 10; i++) fib += i; Console.WriteLine(fib);

Solution

1. Step 1: Understand space optimization

   We only need last two Fibonacci numbers to compute the next, so store them in variables a and b.

2. Step 2: Analyze the correct code logic

   int a = 0, b = 1, c = 0; for (int i = 2; i <= 10; i++) { c = a + b; a = b; b = c; } Console.WriteLine(c); correctly updates a and b in each iteration and stores current Fibonacci in c, printing c after loop.

3. Step 3: Check other options

   int[] dp = new int[10]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= 10; i++) dp[i] = dp[i - 1] + dp[i - 2]; Console.WriteLine(dp[10]); uses array (not O(1) space), the code with loop i < 10 updates variables incorrectly, the code with fib += i sums numbers instead of Fibonacci.

4. Final Answer:

   int a = 0, b = 1, c = 0; for (int i = 2; i <= 10; i++) { c = a + b; a = b; b = c; } Console.WriteLine(c); -> Option B

5. Quick Check:

   Use two vars to save space = B [OK]

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

Common Mistakes:

• Using full array instead of variables
• Incorrect variable updates causing wrong output
• Summing indices instead of Fibonacci numbers