The Core Insight
Recursion is a powerful tool, but naive recursion can be catastrophically slow. Consider computing fib(40) with pure recursion: the call tree branches into two sub-calls at every level, recomputing fib(2), fib(3), and so on millions of times. The root problem is not recursion itself — it is redundant work.
Dynamic programming (DP) is the discipline of recognising and eliminating that redundancy. It applies whenever a problem has two structural properties:
- Overlapping subproblems — the same smaller problem appears more than once in the recursion tree.
- Optimal substructure — an optimal solution to the whole problem can be built from optimal solutions to its subproblems.
When both hold, you can compute each subproblem exactly once, store the answer, and reuse it every subsequent time it is needed. An exponential algorithm collapses to polynomial.
Two Styles: Memoization vs. Tabulation
There are two canonical ways to apply DP. They are equivalent in what they compute; they differ in how they get there.
Top-down: Memoization
Keep the recursive structure, but add a cache. The first time you encounter a subproblem you solve it recursively and store the result. Every subsequent call just looks up the cache.
This is memoization — the same word as "memo" (a note to yourself), not "memorization". The call tree still branches, but each branch terminates immediately after the first visit. Total work: O(n) calls, each O(1). See the full worked example in the Fibonacci Memoization article.
Bottom-up: Tabulation
Instead of recursing top-down, fill a table of answers starting from the smallest subproblems and building toward the answer you need. No recursion, no call-stack overhead — just a loop.
dp[i] holds the i-th Fibonacci number, computed from the two entries below it. We never revisit a subproblem.
Space optimisation. The recurrence only reads the previous two entries, so we can drop the full array and roll two variables:
This reduces space from O(n) to O(1). The trade-off: you lose random access to intermediate answers (useful if the recurrence looks further back).
Complexity
| Version | Time | Space | Notes |
|---|---|---|---|
| Naive recursion | O(2ⁿ) | O(n) stack | Recomputes everything |
| Memoization | O(n) | O(n) cache + O(n) stack | Simple to write |
| Tabulation | O(n) | O(n) table | No recursion overhead |
| Rolling variables | O(n) | O(1) | Only works when recurrence has constant lookback |
When Does DP Apply?
Ask two questions:
- "Am I solving the same sub-problem more than once?" If you draw the recursion tree and see repeated identical calls, the answer is yes.
- "Can I build a global optimum from local optima?" For counting, sum, min, or max problems this usually holds. For problems requiring backtracking (e.g. exact enumeration of all paths) it often does not.
Problems that commonly admit DP: Fibonacci numbers and their generalisations, the 0/1 knapsack and related packing problems, shortest-path in DAGs, string edit distances (LCS, LIS, edit distance), and partition/subset-sum problems.
Interactive Lab
Watch the memoized Fibonacci in action. Notice how the call tree is truncated — each subproblem appears only once despite the overlapping structure.
Key Takeaways
- DP = memoization or tabulation over a recurrence with overlapping subproblems + optimal substructure.
- Top-down memoization is closest to natural recursion — easy to derive, but carries call-stack overhead.
- Bottom-up tabulation fills the table in dependency order — no recursion, and space can sometimes be compressed.
- Both approaches turn exponential work into polynomial work by ensuring each subproblem is computed once.
- The art of DP is defining the subproblem clearly: once the recurrence is stated, the rest is mechanical.