1️⃣ Fibonacci - DP Fundamentals

🟢 BeginnerDP Pattern: 1D

📋 Problem Statement

Given an integer n, return the nth Fibonacci number. F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n > 1.

💼 Real Interview Example

"Write a function to compute the 50th Fibonacci number efficiently." (Amazon, Microsoft)

🔴 Approach 1: Naive Recursion - O(2ⁿ)

function fibNaive(int $n): int {
    if ($n <= 1) return $n;
    return fibNaive($n - 1) + fibNaive($n - 2);
}
// n=50: ~35 years to compute! 💀
// Tree of calls has 2ⁿ nodes, massive repeated work

🟡 Approach 2: Memoization (Top-Down) - O(n)

function fibMemo(int $n, array &$memo = []): int {
    if ($n <= 1) return $n;                    // Base case
    if (isset($memo[$n])) return $memo[$n];     // Cache hit!
    return $memo[$n] = fibMemo($n-1, $memo) + fibMemo($n-2, $memo);
}
// n=50: instant! Each n computed only once
// Time: O(n), Space: O(n) for memo + call stack

🟢 Approach 3: Tabulation (Bottom-Up) - O(n)

function fibTab(int $n): int {
    if ($n <= 1) return $n;
    $dp = [0, 1];  // dp[0]=0, dp[1]=1
    for ($i = 2; $i <= $n; $i++) {
        $dp[$i] = $dp[$i-1] + $dp[$i-2];
    }
    return $dp[$n];
}
// Time: O(n), Space: O(n)

⭐ Approach 4: Space Optimized - O(1) Space

function fibOptimized(int $n): int {
    if ($n <= 1) return $n;
    $prev2 = 0; $prev1 = 1;
    for ($i = 2; $i <= $n; $i++) {
        $current = $prev1 + $prev2;
        $prev2 = $prev1;
        $prev1 = $current;
    }
    return $prev1;
}
// Time: O(n), Space: O(1) - only 3 variables!

📝 Dry Run: fib(5)

i prev2 prev1 current
Init 0 1 -
2 1 1 1
3 1 2 2
4 2 3 3
5 3 5 5 ✅

📊 Complexity Comparison

Naive Recursion O(2ⁿ) O(n) stack
Memoization O(n) O(n) memo + stack
Tabulation O(n) O(n) table
Space Optimized O(n) O(1)

🎯 Interview Variations

  • Climbing Stairs: You can climb 1 or 2 steps. How many ways to reach step n? (Same as Fibonacci!)
  • Tiling Problem: Tile a 2×n board with 2×1 tiles. Number of ways = F(n+1).
  • Hop Problem: Can hop 1, 2, or 3 steps. Ways to reach n? F(n) with modified recurrence.

🔗 Similar Problems

All DP Problems