Fibonacci by dynamic programming

The Fibonacci numbers start 0, 1, 1, 2, 3, 5, 8, 13, ... where each number is the sum of the two before it. They are the textbook first example of dynamic programming, not because they are important in themselves, but because they show the whole idea in miniature: a naive recursion that is catastrophically slow, an overlap that explains the slowness, and a one-line cache that fixes it. If you understand why the slow version is slow and the fast version is fast, you understand the core of DP.

The defining recurrence is fib(n) = fib(n-1) + fib(n-2), with base cases fib(0) = 0 and fib(1) = 1. Coded directly as recursion, this is correct but takes about 2^n calls, because fib(n-2) is recomputed by both fib(n-1) and fib(n) and the duplication explodes down the tree (this is overlapping subproblems in their purest form). Dynamic programming notices there are only n+1 distinct values to ever compute. Top-down, you add a memo so each fib(k) runs once: O(n) time. Bottom-up, you fill an array f[0..n] with f[i] = f[i-1] + f[i-2] in increasing i: also O(n) time. And since each f[i] needs only the two cells before it, you can throw the array away and keep two rolling variables, giving O(n) time and O(1) extra space.

Fibonacci is worth dwelling on because every concept that scales up to hard DPs appears here cleanly: the state is just the index n; the transition is the addition of two predecessors; the base cases are the two seeds; the evaluation order is i increasing; and the space optimization (two variables) is the rolling-array idea in its simplest dress. It also delivers an honest lesson about asymptotics: the naive O(2^n) and the DP O(n) give identical answers, but for n = 50 one finishes instantly while the other does over a billion calls — same output, wildly different cost. (As an aside, even faster methods exist — a matrix-power formula runs in O(log n) — but those are outside the basic DP story.)