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 an array to store Fibonacci numbers from 0 to n, starting with base cases, then fill the array step-by-step using previous two values.

Execution Sample

DSA C

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

💡 Reached i = n = 5, dp array fully computed, returned dp[5]

Variable Tracker

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

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 set before the loop (see steps 1 and 2 in execution_table). Starting from 2 avoids overwriting these known values.

Why do we add dp[i-1] and dp[i-2] to get dp[i]?

Fibonacci numbers are defined as sum of two previous numbers. The execution_table rows 3 to 6 show dp[i] calculated as dp[i-1] + dp[i-2].

What happens if n is 0 or 1?

The function returns dp[0] or dp[1] directly as base cases without entering the loop, as shown in steps 1 and 2.

Visual Quiz - 3 Questions

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

A 1

B 3

C 2

D 5

💡 Hint

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

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

A Step 5

B Step 4

C Step 6

D Step 7

💡 Hint

Look at the 'dp Array State' column in execution_table to see when 3 appears.

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

A 1

B 2

C 3

D 4

💡 Hint

dp[2] = dp[1] + dp[0], so changing dp[1] affects dp[2] calculation at Step 3.

Concept Snapshot

Fibonacci Using DP:
- Use an array dp to store Fibonacci numbers up to n
- Set dp[0]=0 and dp[1]=1 as base cases
- For i from 2 to n, dp[i] = dp[i-1] + dp[i-2]
- Return dp[n] as the result
- Efficient: avoids repeated calculations by storing results

Full Transcript

This visualization shows how to calculate Fibonacci numbers using dynamic programming. We create an array dp to store Fibonacci values from 0 to n. We start by setting dp[0] to 0 and dp[1] to 1 as base cases. Then, for each index i from 2 to n, we calculate dp[i] by adding the two previous values dp[i-1] and dp[i-2]. This way, we build the Fibonacci sequence step-by-step without repeating calculations. The execution table tracks each step, showing how the dp array fills up. The variable tracker shows how the index i and dp array values change over time. Key moments clarify why we start from index 2, why we add previous two values, and what happens for small n. The quiz tests understanding of dp values at specific steps and effects of changing base cases. This method is efficient and easy to understand for beginners.

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 stores intermediate results to avoid repeated calculations

B. It uses more memory without improving speed

C. It calculates Fibonacci numbers randomly

D. It only works for small Fibonacci numbers

Solution

1. Step 1: Understand recursion vs DP

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

2. Step 2: Role of DP in Fibonacci

   DP saves previously calculated Fibonacci values in a table (memoization or tabulation), avoiding repeated work.

3. Final Answer:

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

4. Quick Check:

   DP = stores results to save time [OK]

Hint: DP saves past answers to speed up Fibonacci [OK]

Common Mistakes:

• Thinking DP uses more memory without speed benefit
• Believing DP calculates numbers randomly
• Assuming DP only works for small inputs

2. Which of the following is the correct way to initialize the base cases in a bottom-up DP approach for Fibonacci in C?

easy

A. int fib[2] = {0, 0};

B. int fib[2] = {1, 1};

C. int fib[2] = {0, 1};

D. int fib[2] = {1, 0};

Solution

1. Step 1: Identify Fibonacci base cases

   Fibonacci sequence starts with fib(0) = 0 and fib(1) = 1.

2. Step 2: Match initialization with base cases

   Array fib[2] = {0, 1} correctly sets fib(0) = 0 and fib(1) = 1.

3. Final Answer:

   int fib[2] = {0, 1}; -> Option C

4. Quick Check:

   Base fib = 0,1 [OK]

Hint: Start fib with 0 and 1 for base cases [OK]

Common Mistakes:

• Swapping the order of 0 and 1
• Setting both base cases to 1
• Initializing both to zero

3. What is the output of the following C code snippet using bottom-up DP to find fib(5)?

int fib[6];
fib[0] = 0;
fib[1] = 1;
for(int i = 2; i <= 5; i++) {
    fib[i] = fib[i-1] + fib[i-2];
}
printf("%d", fib[5]);

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Calculate Fibonacci values step-by-step

   fib[0]=0, fib[1]=1 fib[2]=1, fib[3]=2, fib[4]=3, fib[5]=5

2. Step 2: Identify fib[5]

   fib[5] is 5 after the loop completes.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Calculate fib stepwise from 0 and 1 [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Starting loop from wrong index
• Off-by-one errors in array indexing

4. Identify the error in this DP Fibonacci code snippet and select the correct fix:

int fib[10];
fib[0] = 0;
fib[1] = 1;
for(int i = 1; i < 10; i++) {
    fib[i] = fib[i-1] + fib[i-2];
}

medium

A. Initialize fib[2] before loop

B. Change loop to start from i = 2

C. Change loop condition to i <= 10

D. No error, code is correct

Solution

1. Step 1: Analyze loop start index

   The loop starts at i=1, but fib[1] is already initialized, so fib[1] gets overwritten incorrectly.

2. Step 2: Correct loop start

   Loop should start at i=2 to use fib[0] and fib[1] for calculation without overwriting base cases.

3. Final Answer:

   Change loop to start from i = 2 -> Option B

4. Quick Check:

   Loop start = 2 fixes overwrite [OK]

Hint: Start loop after base cases to avoid overwrite [OK]

Common Mistakes:

• Starting loop at 1 overwrites fib[1]
• Not initializing base cases properly
• Using wrong loop end condition

5. You want to find the 10th Fibonacci number using DP but with optimized space using only two variables instead of an array. Which code snippet correctly implements this?

hard

A. int a = 0, b = 1, c, n = 10;
for(int i = 0; i < n; i++) {
c = a + b;
a = c;
b = a;
}
printf("%d", c);

B. int a = 0, b = 1, c, n = 10;
for(int i = 1; i < n; i++) {
c = a + b;
b = a;
a = c;
}
printf("%d", a);

C. int a = 1, b = 1, c, n = 10;
for(int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
printf("%d", c);

D. int a = 0, b = 1, c, n = 10;
for(int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
printf("%d", b);

Solution

1. Step 1: Understand space optimization

   Only two variables (a, b) track last two Fibonacci numbers; c stores current sum.

2. Step 2: Check loop and updates

   Loop from 2 to n, update c = a + b, then shift a = b, b = c correctly to move forward.

3. Final Answer:

   Code snippet A correctly implements optimized Fibonacci calculation -> Option D

4. Quick Check:

   Two vars + sum update = correct [OK]

Hint: Use two vars and update in loop for space optimization [OK]

Common Mistakes:

• Swapping updates of a and b incorrectly
• Wrong loop range causing off-by-one errors
• Initializing variables incorrectly