Dynamic Programming

def fibonacci_naive(n):
    """
    Naive recursive approach - VERY SLOW!
    Time: O(2^n) - exponential
    Space: O(n) - recursion stack
    
    Problem: Recalculates same values many times
    fib(5) calls fib(3) twice, fib(2) three times, etc.
    """
    if n < 0:
        raise ValueError("n must be non-negative")
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

# For n=40, this takes several seconds!
print(fibonacci_naive(10))  # 55

import java.math.BigInteger;

public class FibonacciNaive {
    /**
     * Naive recursive approach - VERY SLOW!
     * Time: O(2^n) - exponential
     * Space: O(n) - recursion stack
     * 
     * Problem: Recalculates same values many times
     * fib(5) calls fib(3) twice, fib(2) three times, etc.
     */
    public static BigInteger fibonacciNaive(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
        if (n <= 1) {
            return BigInteger.valueOf(n);
        }
        return fibonacciNaive(n - 1).add(fibonacciNaive(n - 2));
    }
    
    public static void main(String[] args) {
        // For n=40, this takes several seconds!
        System.out.println(fibonacciNaive(10));  // 55
    }
}

def fibonacci_memo(n, memo=None):
    """
    Top-down DP with memoization
    Time: O(n) - each subproblem solved once
    Space: O(n) - memo dictionary + recursion stack
    
    Stores results to avoid recalculation
    """
    if n < 0:
        raise ValueError("n must be non-negative")
    if memo is None:
        memo = {}
    
    # Check if already computed
    if n in memo:
        return memo[n]
    
    # Base cases
    if n <= 1:
        return n
    
    # Compute and store
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

# For n=40, this is instant!
print(fibonacci_memo(100))  # 354224848179261915075

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class FibonacciMemo {
    /**
     * Top-down DP with memoization
     * Time: O(n) - each subproblem solved once
     * Space: O(n) - memo map + recursion stack
     * 
     * Stores results to avoid recalculation
     */
    public static BigInteger fibonacciMemo(int n, Map<Integer, BigInteger> memo) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
        // Check if already computed
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        // Base cases
        if (n <= 1) {
            return BigInteger.valueOf(n);
        }
        
        // Compute and store
        BigInteger result = fibonacciMemo(n - 1, memo).add(fibonacciMemo(n - 2, memo));
        memo.put(n, result);
        return result;
    }
    
    public static void main(String[] args) {
        Map<Integer, BigInteger> memo = new HashMap<>();
        BigInteger expected = new BigInteger("354224848179261915075");
        if (!fibonacciMemo(100, memo).equals(expected)) throw new AssertionError();
    }
}

def fibonacci_tabulation(n):
    """
    Bottom-up DP with tabulation
    Time: O(n) - single loop
    Space: O(n) - dp array
    
    Builds solution iteratively from base cases
    """
    if n < 0:
        raise ValueError("n must be non-negative")
    if n <= 1:
        return n
    
    # Create table
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    
    # Fill table bottom-up
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

print(fibonacci_tabulation(100))  # 354224848179261915075

import java.math.BigInteger;

public class FibonacciTabulation {
    /**
     * Bottom-up DP with tabulation
     * Time: O(n) - single loop
     * Space: O(n) - dp array
     * 
     * Builds solution iteratively from base cases
     */
    public static BigInteger fibonacciTabulation(int n) {
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
        if (n <= 1) {
            return BigInteger.valueOf(n);
        }
        
        // Create table
        BigInteger[] dp = new BigInteger[n + 1];
        dp[0] = BigInteger.ZERO;
        dp[1] = BigInteger.ONE;
        
        // Fill table bottom-up
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1].add(dp[i - 2]);
        }
        
        return dp[n];
    }
    
    public static void main(String[] args) {
        BigInteger expected = new BigInteger("354224848179261915075");
        if (!fibonacciTabulation(100).equals(expected)) throw new AssertionError();
    }
}