Fibonacci Using DP in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the base case for Fibonacci.

DSA C#

int[] fib = new int[n + 1];
fib[0] = [1];

Drag options to blanks, or click blank then click option'

A0

B1

C-1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Setting fib[0] to 1 instead of 0.

Using uninitialized values.

The Fibonacci sequence starts with 0 at index 0.

2fill in blank

medium

Complete the code to initialize the second base case for Fibonacci.

DSA C#

fib[1] = [1];

Drag options to blanks, or click blank then click option'

A0

B1

C2

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting fib[1] to 0 instead of 1.

Skipping initialization of fib[1].

The second Fibonacci number is 1 at index 1.

3fill in blank

hard

Fix the error in the loop to correctly compute Fibonacci numbers.

DSA C#

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

Drag options to blanks, or click blank then click option'

A+

B/

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Using division which is incorrect for Fibonacci.

Each Fibonacci number is the sum of the two previous numbers.

4fill in blank

hard

Fill both blanks to complete the method that returns the nth Fibonacci number using DP.

DSA C#

public int Fibonacci(int n) {
    int[] fib = new int[n + 1];
    fib[0] = 0;
    fib[1] = 1;
    for (int i = [1]; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - [2]];
    }
    return fib[n];
}

Drag options to blanks, or click blank then click option'

A2

B1

C0

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Starting loop at 1 or 0 instead of 2.

Using wrong index subtraction in fib array.

The loop starts at 2 because fib[0] and fib[1] are base cases. The second blank is 2 to get fib[i-2].

5fill in blank

hard

Fill all three blanks to create a dictionary that maps each index to its Fibonacci number for n, filtering only those greater than 0.

DSA C#

var fibDict = new Dictionary<int, int>();
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 1 - [1]];
}
foreach (var i in Enumerable.Range(0, n + 1)) {
    if (fib[i] [2] 0) {
        fibDict[[3]] = fib[i];
    }
}

Drag options to blanks, or click blank then click option'

A1

B>

Ci

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong subtraction index in Fibonacci calculation.

Using wrong comparison operator in if condition.

Using wrong key in dictionary assignment.

Subtract 1 to get the previous Fibonacci number in the sum. Filter Fibonacci numbers greater than 0. Use i as the key in the dictionary.

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