Fibonacci Using DP in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci DP Array After Execution

What is the content of the DP array after computing fibonacci(6) using bottom-up dynamic programming?

DSA C#

int[] FibonacciDP(int n) {
    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];
    }
    return dp;
}

var result = FibonacciDP(6);
Console.WriteLine(string.Join(", ", result));

A 0, 1, 2, 3, 5, 8, 13

B 0, 1, 1, 3, 4, 7, 11

C 1, 1, 2, 3, 5, 8, 13

D 0, 1, 1, 2, 3, 5, 8

💡 Hint

Remember the Fibonacci sequence starts with 0 and 1, and each next number is the sum of the previous two.

The DP array stores Fibonacci numbers from 0 to n. Starting with dp[0]=0 and dp[1]=1, each dp[i] is dp[i-1] + dp[i-2]. For n=6, the array is [0,1,1,2,3,5,8].

🧠 Conceptual

intermediate

Why Use DP for Fibonacci?

Why is dynamic programming preferred over simple recursion for calculating Fibonacci numbers?

A DP stores intermediate results to avoid repeated calculations, improving efficiency.

B DP uses less memory than recursion because it does not use a call stack.

C DP always uses less code than recursion.

D DP calculates Fibonacci numbers randomly to speed up the process.

💡 Hint

Think about how recursion repeats the same calculations many times.

Dynamic programming saves results of smaller problems (memoization or tabulation) so they are not recalculated, making the process faster than naive recursion.

🔧 Debug

advanced

Identify the Error in Fibonacci DP Code

What error will this code produce when calling FibonacciDP(5)? int FibonacciDP(int n) { 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]; } return dp[n]; }

A Returns 5 correctly without error

B NullReferenceException because dp is not initialized

C IndexOutOfRangeException because dp array size is n but code accesses dp[n]

D Compilation error due to missing return statement

💡 Hint

Check the size of the dp array and the highest index accessed.

The dp array is created with size n, so valid indices are 0 to n-1. Accessing dp[n] causes IndexOutOfRangeException.

❓ Predict Output

advanced

Output of Fibonacci Using Memoization

What is the output of the following code when calling FibonacciMemo(5)?

DSA C#

int FibonacciMemo(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = FibonacciMemo(n - 1, memo) + FibonacciMemo(n - 2, memo);
    return memo[n];
}

int n = 5;
int[] memo = new int[n + 1];
for (int i = 0; i <= n; i++) memo[i] = -1;
int result = FibonacciMemo(n, memo);
Console.WriteLine(result);

A 3

B 5

C 13

D 8

💡 Hint

Fibonacci(5) is the 5th Fibonacci number starting from 0 index.

Fibonacci sequence starting from 0: 0,1,1,2,3,5,... The 5th number (index 5) is 5.

🧠 Conceptual

expert

Time Complexity of Fibonacci DP Approaches

What is the time complexity of calculating the nth Fibonacci number using bottom-up dynamic programming compared to naive recursion?

A Bottom-up DP is O(n), naive recursion is O(2^n)

B Bottom-up DP is O(n^2), naive recursion is O(n)

C Bottom-up DP is O(log n), naive recursion is O(n^2)

D Both bottom-up DP and naive recursion are O(n)

💡 Hint

Consider how many times each Fibonacci number is calculated in each approach.

Bottom-up DP calculates each Fibonacci number once, so O(n). Naive recursion recalculates many subproblems exponentially, O(2^n).

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