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]
1	Initialize dp[0]	0	[0, _, _, _, _, _, _, _]	Set dp[0] = 0	0
2	Initialize dp[1]	1	[0, 1, _, _, _, _, _, _]	Set dp[1] = 1	1
3	Calculate dp[2]	2	[0, 1, _, _, _, _, _, _]	dp[2] = dp[1] + dp[0] = 1 + 0	1
4	Calculate dp[3]	3	[0, 1, 1, _, _, _, _, _]	dp[3] = dp[2] + dp[1] = 1 + 1	2
5	Calculate dp[4]	4	[0, 1, 1, 2, _, _, _, _]	dp[4] = dp[3] + dp[2] = 2 + 1	3
6	Calculate dp[5]	5	[0, 1, 1, 2, 3, _, _, _]	dp[5] = dp[4] + dp[3] = 3 + 2	5
7	Calculate dp[6]	6	[0, 1, 1, 2, 3, 5, _, _]	dp[6] = dp[5] + dp[4] = 5 + 3	8
8	Calculate dp[7]	7	[0, 1, 1, 2, 3, 5, 8, _]	dp[7] = dp[6] + dp[5] = 8 + 5	13
9	Return result	7	[0, 1, 1, 2, 3, 5, 8, 13]	Return dp[7]	13

💡 Loop ends after i reaches n=7, dp array fully computed.

Variable Tracker

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

Key Moments - 3 Insights

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

These are the base cases of Fibonacci. Without them, dp[i-1] and dp[i-2] would be undefined in the first loop iteration (see steps 1 and 2 in execution_table).

Why does the loop start from i = 2 and not from 0 or 1?

Because dp[0] and dp[1] are already known base cases. Starting at 2 lets us build new values from these known values (see step 3 in execution_table).

How does dp[i] depend on previous values?

Each dp[i] is the sum of dp[i-1] and dp[i-2], so we must have those values computed before calculating dp[i] (see calculation column in execution_table rows 3 to 8).

Visual Quiz - 3 Questions

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

A 3

B 5

C 2

D 1

💡 Hint

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

At which step does the loop finish computing dp[7]?

A Step 9

B Step 7

C Step 8

D Step 6

💡 Hint

Look at the 'Index i' and 'Step' columns in execution_table to find when i=7 is computed.

If we change dp[0] to 1, what would be the value of dp[2] at Step 3?

A 1

B 2

C 0

D 3

💡 Hint

dp[2] = dp[1] + dp[0], so changing dp[0] affects dp[2] (see calculation in Step 3).

Concept Snapshot

Fibonacci Using DP:
- Use an 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]
- Efficient: O(n) time, O(n) space

Full Transcript

This visualization shows how to compute the Fibonacci number for n=7 using dynamic programming. We start by creating an array dp to store Fibonacci numbers from 0 to 7. We set the first two values dp[0]=0 and dp[1]=1 as base cases. Then, we fill the array from index 2 to 7, each time calculating dp[i] as the sum of the two previous values dp[i-1] and dp[i-2]. The execution table tracks each step, showing the dp array state and calculations. The variable tracker shows how the index i and dp values change after each step. Key moments clarify why base cases are needed and why the loop starts at 2. The quiz tests understanding of dp values at specific steps and effects of changing base cases. This method efficiently computes Fibonacci numbers in linear time and space.

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 using only addition.

D. It uses a recursive function without any loops.

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 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 = store results to avoid repeats [OK]

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

Common Mistakes:

• Thinking DP uses less memory than recursion
• Confusing DP with simple recursion
• Believing DP avoids addition operations

2. Which of the following C++ code snippets correctly initializes the base cases for Fibonacci using bottom-up DP?

easy

A. int fib[10]; fib[0] = 0; fib[1] = 1;

B. int fib[10]; fib[1] = 0; fib[2] = 1;

C. int fib[10]; fib[0] = 1; fib[1] = 1;

D. int fib[10]; fib[0] = 1; fib[2] = 0;

Solution

1. Step 1: Identify Fibonacci base cases

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

2. Step 2: Check initialization correctness

   int fib[10]; fib[0] = 0; fib[1] = 1; correctly sets fib[0] = 0 and fib[1] = 1, matching the base cases.

3. Final Answer:

   int fib[10]; fib[0] = 0; fib[1] = 1; -> Option A

4. Quick Check:

   fib[0]=0, fib[1]=1 base cases [OK]

Hint: Base cases: fib[0]=0 and fib[1]=1 [OK]

Common Mistakes:

• Starting fib from index 1 instead of 0
• Swapping values of fib[0] and fib[1]
• Initializing wrong indices

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

int fib[6];
fib[0] = 0; fib[1] = 1;
for(int i = 2; i < 6; i++) {
    fib[i] = fib[i-1] + fib[i-2];
}
std::cout << fib[5];

medium

A. 5

B. 8

C. 13

D. 21

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 output

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

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib[5]=5 [OK]

Hint: Calculate fib stepwise from base cases [OK]

Common Mistakes:

• Confusing fib[5] with fib[6]
• Off-by-one errors in loop
• Incorrect addition order

4. Identify the error in the following Fibonacci DP code and choose 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];
}
std::cout << fib[9];

medium

A. Change loop condition to i <= 10

B. Initialize fib[2] before the loop

C. Change fib[0] to 1

D. Change loop start to i = 2

Solution

1. Step 1: Analyze loop start index

   The loop starts at i=1, but fib[1] is already initialized. Calculating fib[1] again causes fib[-1] access (invalid).

2. Step 2: Correct loop start

   Loop should start at i=2 to use fib[i-1] and fib[i-2] safely.

3. Final Answer:

   Change loop start to i = 2 -> Option D

4. Quick Check:

   Loop from i=2 avoids invalid index [OK]

Hint: Start loop at 2 to avoid negative index [OK]

Common Mistakes:

• Starting loop at 1 causing invalid access
• Changing base case values incorrectly
• Extending loop beyond array size

5. You want to find the 50th Fibonacci number using DP in C++. Which approach is best to handle large Fibonacci numbers efficiently and why?

hard

A. Use bottom-up DP with int array since int can hold large numbers.

B. Use simple recursion without memoization for clarity.

C. Use a vector of unsigned long long and bottom-up DP to avoid recursion overhead.

D. Use recursion with memoization but store results in int array.

Solution

1. Step 1: Consider data type size

   50th Fibonacci number is very large; int cannot hold it, unsigned long long can hold bigger values.

2. Step 2: Choose DP approach

   Bottom-up DP avoids recursion overhead and stack issues, making it efficient for large n.

3. Final Answer:

   Use a vector of unsigned long long and bottom-up DP to avoid recursion overhead. -> Option C

4. Quick Check:

   Big number + bottom-up DP = efficient and safe [OK]

Hint: Use big data type and bottom-up DP for large n [OK]

Common Mistakes:

• Using int causing overflow
• Using recursion causing stack overflow
• Ignoring data type limits