Fibonacci Using DP in DSA C#

Mental Model

Remember past Fibonacci numbers so you don't calculate them again.

Analogy: Like writing down answers on a notepad so you don't solve the same puzzle twice.

fib[0] = 0
fib[1] = 1
fib[2] = ?
fib[3] = ?
fib[4] = ?
...

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using DP

Goal: Find the 5th Fibonacci number efficiently by storing previous results

Step 1: Initialize fib array with fib[0]=0 and fib[1]=1

fib: [0, 1, ?, ?, ?, ?]

Why: Base cases are known and needed to build next numbers

Step 2: Calculate fib[2] = fib[1] + fib[0] = 1 + 0 = 1

fib: [0, 1, 1, ?, ?, ?]

Why: Use stored values to find next Fibonacci number

Step 3: Calculate fib[3] = fib[2] + fib[1] = 1 + 1 = 2

fib: [0, 1, 1, 2, ?, ?]

Why: Build on previous results to avoid repeated work

Step 4: Calculate fib[4] = fib[3] + fib[2] = 2 + 1 = 3

fib: [0, 1, 1, 2, 3, ?]

Why: Continue filling array with known sums

Step 5: Calculate fib[5] = fib[4] + fib[3] = 3 + 2 = 5

fib: [0, 1, 1, 2, 3, 5]

Why: Final Fibonacci number for n=5 found using stored values

Result:

fib: [0, 1, 1, 2, 3, 5]
Answer: 5

Annotated Code

DSA C#

using System;

class FibonacciDP
{
    public static int Fib(int n)
    {
        if (n <= 1) return n; // base cases
        int[] fib = new int[n + 1];
        fib[0] = 0; // fib(0)
        fib[1] = 1; // fib(1)
        for (int i = 2; i <= n; i++)
        {
            fib[i] = fib[i - 1] + fib[i - 2]; // sum of two previous
        }
        return fib[n];
    }

    static void Main()
    {
        int n = 5;
        int result = Fib(n);
        Console.WriteLine(result);
    }
}

if (n <= 1) return n; // base cases

return known Fibonacci values for 0 and 1

fib[0] = 0; // fib(0) fib[1] = 1; // fib(1)

initialize base Fibonacci numbers

for (int i = 2; i <= n; i++) { fib[i] = fib[i - 1] + fib[i - 2]; // sum of two previous }

build Fibonacci numbers from bottom up using stored results

return fib[n];

return the nth Fibonacci number after computation

Output

5

Complexity Analysis

Time: O(n) because we calculate each Fibonacci number once from 2 to n

Space: O(n) because we store all Fibonacci numbers up to n in an array

vs Alternative: Compared to naive recursion which is O(2^n), DP is much faster by avoiding repeated calculations

Edge Cases

n = 0

Returns 0 immediately as base case

DSA C#

if (n <= 1) return n; // base cases

n = 1

Returns 1 immediately as base case

DSA C#

if (n <= 1) return n; // base cases

n is large (e.g., 50)

Calculates efficiently without repeated work, but uses more memory

DSA C#

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

When to Use This Pattern

When you see repeated calculations of Fibonacci or similar sequences, use DP to store past results and avoid recomputation.

Common Mistakes

Mistake: Using naive recursion without memoization causing slow exponential time
Fix: Use an array to store results and build up from base cases iteratively

Mistake: Not handling base cases n=0 or n=1 correctly
Fix: Add condition to return n immediately if n <= 1

Summary

Calculates Fibonacci numbers efficiently by storing previous results.

Use when you need Fibonacci numbers or similar sequences without repeated work.

Remember to build from base cases and store all results to avoid repeated calculations.

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