Fibonacci numbers

Fibonacci is the canonical DP warm-up because it exposes the exact mechanism every DP problem exploits: a state (n) whose answer depends on two smaller instances of the same subproblem, and those subproblems overlap massively as recursion unwinds — so caching (or building bottom-up) collapses exponential work into linear work.

Recognize the pattern

• The recurrence f(n) = f(n-1) + f(n-2) references smaller instances of the same function — a self-referential recurrence, not just "loop and accumulate".
• Naive recursion re-computes identical calls: f(5) calls f(3) twice, f(2) three times, etc. — the tell for "overlapping subproblems", the hallmark of DP.
• The state space is 1-dimensional and each state depends only on a fixed-size window of prior states (here, the last two) — the tell that you can drop a full table for O(1) rolling variables.

Brute force → optimal

Brute force (naive recursion): directly translate the recurrence into a function that calls itself twice per level, with no memory of past calls.

static long fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

This rebuilds the entire call tree every time a subproblem recurs, costing exponential time and O(n) space just for the recursion stack.

Optimal (bottom-up tabulation, rolling variables): observe that computing f(n) only ever needs the last two values, so iterate forward and keep two running variables instead of a tree or even a full array.

static long fibDP(int n) {
    if (n <= 1) return n;
    long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        long curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Complexity, derived

Naive recursion: let T(n) be the number of calls to compute f(n). T(n) = T(n-1) + T(n-2) + 1, with T(0)=T(1)=1. This is itself Fibonacci-shaped, and since consecutive Fibonacci ratios converge to φ ≈ 1.618, T(n) grows as Θ(φⁿ) — exponential time. Space is O(n) for the deepest recursion stack (the chain of pending f(n-1) calls).

Bottom-up: the loop body does a fixed number of operations (one add, two assignments) and runs exactly n-1 times → Θ(n) time. Only two scalars are kept alive at once → O(1) auxiliary space (a full memo array would be O(n) space instead).

Traced example: fib(6)

Result: fib(6) = 8, matching 0,1,1,2,3,5,8. Each row overwrites prev2/prev1 rather than growing a table.

Pitfalls

• Naive recursion without memoization on n as small as 40 already takes seconds — always check for the self-referential recurrence before coding the direct translation.
• Fibonacci grows fast: fib(93) already overflows a signed 64-bit long. Confirm the constraint range (here n ≤ 30, safely within int) before picking a numeric type.
• Off-by-one on the base cases (Fib(0)=0, Fib(1)=1) is the most common bug; the loop trace above pins the exact starting values.
• Top-down memoization is asymptotically equal to bottom-up but still pays O(n) recursion-stack space — don't assume memoizing alone gives O(1) space.

When to use / when not — trade-offs

Rolling-variable bottom-up (this page): use whenever only the last k states are needed and you want a single final answer — O(n) time, O(1) space, no recursion overhead.

vs. Top-down memoization: easier to write when the recursion is irregular or has many branches (e.g., not a clean linear chain), and it computes only the states actually needed rather than all of 0..n; but it costs O(n) stack space and function-call overhead vs. tight loop iterations.

vs. Matrix exponentiation / fast doubling: use when n is huge (n ~ 10^9 or more) and only the final value is needed — O(log n) time by repeated squaring of the transformation matrix [[1,1],[1,0]]; not worth the complexity for small, bounded n like this problem's n ≤ 30.

vs. Closed-form (Binet's formula): O(1) time using powers of the golden ratio, but suffers floating-point precision loss for larger n — unreliable for exact integer answers beyond small n.

Takeaways

• Overlapping subproblems in a self-referential recurrence is the signal for DP; exponential naive recursion becomes linear once results are reused.
• When a state only depends on a fixed small window of previous states, drop the table for rolling scalars to get O(1) space.
• Always sanity-check the numeric type against how fast the recurrence grows relative to the given constraints — for exact values past fib(92) switch to BigInteger, or if the problem asks for the answer modulo some m, reduce every addition mod m.

Recall: Why does naive recursive Fibonacci take exponential time, and what single change makes it linear?

Source: adapted from standard interview-prep Fibonacci problem statement and standard dynamic-programming derivations.