509.Fibonacci Number

📘 LeetCode 509: Fibonacci Number & Memoization

📌 Problem Overview

• Problem Number: 509
• Problem Name: Fibonacci Number & Memoization
• Difficulty: Easy
• Category: 1D Dynamic Programming
• Runnable Source: Program.cs

---

💡 Algorithmic Approach & Pattern

This problem is solved using the 1D Dynamic Programming algorithmic pattern.

Key Insights & Invariants:

1. Identify the input constraints and edge conditions.
2. Structure the data flow to minimize unnecessary traversals and heap reallocations.
3. Validate corner cases (empty collections, single-element cases, duplicates, extremes).

---

💻 Verified C# Implementation (.NET 9)

The solution is verified and executable via the companion project in src/note-sum-fibonacci/:

Dictionary<int, int> memo = new Dictionary<int, int>();
Console.WriteLine(Fib(9));
Console.WriteLine(FibRecursive(9));
// Console.WriteLine(FibDynamicProgramming(9));
 
 
// 1 1 2 3 5 8 13 21 34 55
 
//  static int calculateSum(int n)
//     {
//         if (n <= 0)
//         return 0;
    
//         int []fibo = new int[n + 1];
//         fibo[0] = 0; fibo[1] = 1;
    
//         // Initialize result
//         int sum = fibo[0] + fibo[1];
    
//         // Add remaining terms
//         for (int i = 2; i <= n; i++)
//         {
//             fibo[i] = fibo[i - 1] + fibo[i - 2];
//             sum += fibo[i];
//         }
    
//         return sum;
//     }
    
 
int Fib(int n)
{
    if (n <= 2)
    {
        return 1;
    }
    int a = 1;
    int b = 1;
    for (int i = 3; i <= n; i++)
    {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}
 
 
int FibRecursive(int n)
{
    if (n <= 2)
    {
        return 1;
    }
    return FibRecursive(n - 1) + FibRecursive(n - 2);
}
int FibMemoized(int n)
{
    if (memo.ContainsKey(n))
    {
        return memo[n];
    }
    if (n <= 2)
    {
        return 1;
    }
    int result = FibMemoized(n - 1) + FibMemoized(n - 2);
    memo[n] = result;
    return result;
}
// 12 13 14
 
 
int FibDynamicProgramming(int n)
{
    Console.WriteLine($"Calculating Fib({n})");
    if (memo.ContainsKey(n))
    {
        Console.WriteLine($"Found Fib({n}) in memo: {memo[n]}");
        return memo[n];
    }
    if (n <= 1)
    {
        Console.WriteLine($"Base case for Fib({n}): {n}");
        return n;
    }
    int result = FibDynamicProgramming(n - 1) + FibDynamicProgramming(n - 2);
    Console.WriteLine($"Calculated Fib({n}) as {result}");
    memo[n] = result;
    return result;
}
 
 
 
// ### `Fib(5)` Calculation Flow with Memoization
 
// | Function Call | Action                             | Memoization Table (`memo`) | Return Value |
// | ------------- | ---------------------------------- | -------------------------- | ------------ |
// | `Fib(5)`      | Needs `Fib(4)` + `Fib(3)`          | `{}`                       |              |
// | `Fib(4)`      | Needs `Fib(3)` + `Fib(2)`          | `{}`                       |              |
// | `Fib(3)`      | Needs `Fib(2)` + `Fib(1)`          | `{}`                       |              |
// | `Fib(2)`      | Needs `Fib(1)` + `Fib(0)`          | `{}`                       |              |
// | `Fib(1)`      | Base case                          | `{}`                       | 1            |
// | `Fib(0)`      | Base case                          | `{}`                       | 0            |
// | `Fib(2)`      | Calculates `1 + 0`. Stores result. | `{2: 1}`                   | 1            |
// | `Fib(1)`      | Base case                          | `{2: 1}`                   | 1            |
// | `Fib(3)`      | Calculates `1 + 1`. Stores result. | `{2: 1, 3: 2}`             | 2            |
// | `Fib(2)`      | **Found in memo!**                 | `{2: 1, 3: 2}`             | 1            |
// | `Fib(4)`      | Calculates `2 + 1`. Stores result. | `{2: 1, 3: 2, 4: 3}`       | 3            |
// | `Fib(3)`      | **Found in memo!**                 | `{2: 1, 3: 2, 4: 3}`       | 2            |
// | `Fib(5)`      | Calculates `3 + 2`. Stores result. | `{2: 1, 3: 2, 4: 3, 5: 5}` | 5            |
 
// As you can see, `Fib(3)` and `Fib(2)` are calculated once, and then their results are reused, which is much more efficient than recalculating them.

---

📊 Complexity Analysis

Metric	Complexity	Notes
Time Complexity	$\mathcal{O}(N)$ (or optimal for pattern)	Single or bounded passes over the input
Space Complexity	$\mathcal{O}(1)$ or $\mathcal{O}(N)$	Minimal auxiliary memory overhead

---

🚨 Edge Cases & Interview Traps

• Empty / Null Input: Ensure null safety and guard clauses.
• Single Element: Confirm the algorithm terminates without out-of-bounds indexing.
• Duplicates & Boundaries: Check duplicate handling and extreme integer limits.