Fibonacci Using DP in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using Dynamic Programming (DP) to calculate Fibonacci numbers?

DP stores the results of smaller subproblems (previous Fibonacci numbers) to avoid repeated calculations, making the process faster and more efficient.

beginner

In Fibonacci DP, what does the 'memoization' technique mean?

Memoization means saving the results of Fibonacci calculations in a table (array) so that when the same value is needed again, it can be retrieved instantly instead of recalculating.

intermediate

What is the time complexity of calculating Fibonacci numbers using DP compared to the naive recursive method?

Using DP, the time complexity is O(n) because each Fibonacci number is calculated once. The naive recursive method has exponential time complexity O(2^n) due to repeated calculations.

intermediate

Why is the bottom-up approach often preferred over the top-down approach in Fibonacci DP?

Bottom-up builds the solution from the smallest subproblems up, using iteration and no recursion, which avoids function call overhead and stack issues, making it more efficient in practice.

beginner

Show the base cases used in Fibonacci DP and explain why they are important.

Base cases: fib(0) = 0 and fib(1) = 1. They are important because they stop the recursion or iteration and provide starting values to build the rest of the Fibonacci sequence.

What does DP store to optimize Fibonacci calculation?

A Prime numbers

B Random numbers

C Only the last Fibonacci number

D Previous Fibonacci numbers

DP stores previous Fibonacci numbers to avoid recalculating them.

What is the time complexity of Fibonacci using DP?

A O(n)

B O(n^2)

C O(2^n)

D O(log n)

DP calculates each Fibonacci number once, so time complexity is O(n).

Which approach uses iteration to build Fibonacci numbers from the bottom up?

A Divide and conquer

B Top-down

C Bottom-up

D Greedy

Bottom-up approach uses iteration starting from base cases.

What are the base cases for Fibonacci DP?

A fib(0)=0, fib(1)=1

B fib(1)=0, fib(2)=1

C fib(0)=1, fib(1)=1

D fib(2)=0, fib(3)=1

Base cases are fib(0)=0 and fib(1)=1 to start the sequence.

Memoization in Fibonacci DP means:

A Ignoring previous results

B Saving results to avoid repeated work

C Using random numbers

D Calculating recursively without storage

Memoization saves results to avoid recalculating the same Fibonacci numbers.

Explain how Dynamic Programming improves the calculation of Fibonacci numbers compared to simple recursion.

Think about how remembering past answers helps.

Describe the difference between top-down and bottom-up approaches in Fibonacci DP.

One starts from the problem and breaks down, the other builds up from the smallest cases.

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