Brute Force Approach for Fibonacci Number

The most intuitive way to solve the Fibonacci Number problem is to directly translate the mathematical recurrence relation into code using recursion.

The algorithm functions as follows:

1. Check if $n$ is 0 or 1. If so, return $n$.
2. Otherwise, recursively call the function for $n-1$ and $n-2$ and return their sum.

python
# Pseudo-code for Brute Force
function fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Why this approach fails: The time complexity of this recursive solution is $O(2^n)$. This exponential growth occurs because the algorithm re-calculates the same subproblems multiple times. For example, to calculate $F(5)$, it calculates $F(4)$ and $F(3)$. However, the calculation of $F(4)$ also calculates $F(3)$. As $n$ increases, the number of redundant operations explodes, leading to a Time Limit Exceeded (TLE) on larger constraints or significant inefficiency on moderate ones.

Core Insight for Fibonacci Number

The core insight needed to move from the brute force approach to the optimal solution is the recognition of overlapping subproblems. In the recursion tree, the value of fib(k) is computed repeatedly for the same k.

By applying the Dynamic Programming pattern, we can eliminate this redundancy. Instead of starting from $n$ and working backward (Top-Down), we start from the base cases ($0$ and $1$) and work forward (Bottom-Up).

Visual Description: Imagine a linear array of size $n+1$. We know the values at index 0 and index 1. To fill index 2, we simply look at the values at indices 0 and 1. To fill index 3, we look at indices 1 and 2. The dependency graph is a simple straight line where node $i$ depends only on $i-1$ and $i-2$. Since we process in increasing order, the values needed for the current step are always available and already computed.

Execution Flow

1. Handle Base Cases: If $n = 0$, return 0. If $n = 1$, return 1.
2. Initialize State:
   • Set prev2 = 0 (corresponds to $F(0)$).
   • Set prev1 = 1 (corresponds to $F(1)$).
3. Iterate: Loop from $i = 2$ up to $n$.
   • Calculate current = prev1 + prev2.
   • Update pointers for the next iteration:
     • prev2 becomes the old prev1.
     • prev1 becomes the calculated current.
4. Return Result: After the loop finishes, prev1 holds the value of $F(n)$.

Proof of Correctness

The correctness is proven via mathematical induction.

• Base Case: The algorithm explicitly handles or initializes correctly for $n=0$ and $n=1$.
• Inductive Step: Assume that at iteration $i$, prev1 correctly holds $F(i-1)$ and prev2 correctly holds $F(i-2)$. The algorithm computes current = prev1 + prev2, which is $F(i-1) + F(i-2)$. By the definition of the Fibonacci sequence, this sum is exactly $F(i)$.
• Termination: The loop terminates at $n$, ensuring the final value stored in prev1 is $F(n)$.

Reference Implementation

C++ Solution for LeetCode 509

cpp
class Solution {
public:
    int fib(int n) {
        // Base cases
        if (n == 0) return 0;
        if (n == 1) return 1;

        // DP state variables
        int prev2 = 0; // F(0)
        int prev1 = 1; // F(1)
        
        // Iterative Bottom-Up Calculation
        for (int i = 2; i <= n; ++i) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
};

Java Solution for LeetCode 509

java
class Solution {
    public int fib(int n) {
        // Base cases
        if (n == 0) return 0;
        if (n == 1) return 1;

        // DP state variables
        int prev2 = 0; // F(0)
        int prev1 = 1; // F(1)

        // Iterative Bottom-Up Calculation
        for (int i = 2; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

Python Solution for LeetCode 509

python
class Solution:
    def fib(self, n: int) -> int:
        # Base cases
        if n == 0:
            return 0
        if n == 1:
            return 1
        
        # DP state variables
        prev2, prev1 = 0, 1
        
        # Iterative Bottom-Up Calculation
        for _ in range(2, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current
            
        return prev1