Fibonacci — memoized + bottom-up + O(1) space.

Problem. Return the nth Fibonacci number, where fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2). This is the "hello world" of DP — the point is to show all three rungs of the optimization ladder.

Brute force — O(2ⁿ) time, O(n) stack

Naive recursion recomputes the same subproblems exponentially often:

int fibNaive(int n) {
    if (n < 2) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);   // fib(n-2) computed twice, etc.
}

The recursion tree has O(φⁿ) nodes for only O(n) distinct values — pure overlapping subproblems.

Memoized (top-down) — O(n) time, O(n) space

Cache each result; null means "not yet computed":

int fib(int n) {
    return fib(n, new Integer[n + 1]);
}
int fib(int n, Integer[] memo) {
    if (n < 2) return n;
    if (memo[n] != null) return memo[n];
    return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}

Each state computed once → linear.

Bottom-up tabulation — O(n) time, O(n) space

int fib(int n) {
    if (n < 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

Optimal — O(n) time, O(1) space

dp[i] reads only the previous two values, so a rolling pair of scalars replaces the whole array:

int fib(int n) {
    if (n < 2) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}