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 efficient.

beginner

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), which is much faster than the naive recursive method's exponential time O(2^n).

beginner

In DP Fibonacci, what data structure is commonly used to store intermediate Fibonacci values?

An array or list is commonly used to store intermediate Fibonacci values for quick access and reuse.

intermediate

Why is the DP approach to Fibonacci considered bottom-up?

Because it starts calculating from the smallest Fibonacci numbers (like 0 and 1) and builds up to the desired number, avoiding recursion.

intermediate

What is the difference between memoization and tabulation in DP for Fibonacci?

Memoization is a top-down approach that uses recursion and caches results, while tabulation is a bottom-up approach that iteratively fills a table.

What is the first step in the bottom-up DP approach to Fibonacci?

A Initialize the first two Fibonacci numbers in an array

B Call the recursive function for n-1

C Calculate Fibonacci using a loop without storing values

D Return 0 immediately

The bottom-up DP approach starts by initializing the first two Fibonacci numbers (0 and 1) in an array to build upon.

Which of these is NOT a benefit of using DP for Fibonacci calculation?

A Stores intermediate results

B Reduces repeated calculations

C Improves time complexity to O(n)

D Uses less memory than recursion

DP uses extra memory to store intermediate results, so it usually uses more memory than naive recursion.

What does the DP array store when calculating Fibonacci numbers?

A Only the last Fibonacci number

B All Fibonacci numbers up to n

C Random numbers

D Only the first Fibonacci number

The DP array stores all Fibonacci numbers from 0 up to n for reuse.

What is the value of Fibonacci(0) in the DP approach?

A 0

B 1

C Undefined

D Depends on n

By definition, Fibonacci(0) is 0.

Which approach uses recursion with caching in Fibonacci DP?

A Tabulation

B Iterative

C Memoization

D Brute force

Memoization is the top-down recursive approach with caching of results.

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

Think about how storing results helps avoid doing the same work again.

Describe the difference between memoization and tabulation in the context of Fibonacci using DP.

One uses recursion, the other uses loops.

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