The core idea
Dynamic programming (DP) is a way to make certain slow recursive problems fast. The insight: many recursions solve the same subproblem over and over. If you solve each subproblem once and store the answer, you never repeat the work — and an exponential algorithm collapses to a polynomial one.
It is not a specific algorithm but a technique, and recognising when it applies is most of the skill.
The two conditions
DP works precisely when a problem has both of these:
Overlapping subproblems — the same smaller problems recur, so caching helps. Optimal substructure — the best solution is built from the best solutions of its subproblems.
Miss either and DP does not apply: with no overlap there is nothing to cache, and with no optimal substructure the pieces do not combine cleanly.
Two ways to do it
Memoization (top-down) keeps the natural recursion but wraps it in a cache: before computing, check whether this subproblem is already solved; if so, return the stored answer. Easy to write from an existing recursive solution.
Tabulation (bottom-up) throws away recursion and fills a table from the smallest subproblems upward, until it reaches the one you want. Usually a little faster and avoids deep recursion, but you must work out the order of filling.
Same answer, opposite direction
Memoization starts at the big problem and recurses down, caching on the way. Tabulation starts at the base cases and builds up. Both compute each subproblem exactly once — which is the whole point.
The problems you will meet
A recognisable family of problems is solved with DP, and questions draw from it: Fibonacci (the classic first example), coin change (fewest coins for an amount), the 0/1 knapsack (best value under a weight limit), and longest common subsequence (how similar two strings are, behind diff tools and DNA alignment).
All share the same shape: a naive recursion that re-explores the same states exponentially, rescued by remembering each state once.
A worked example
The naive recursive Fibonacci is fib(n) = fib(n−1) + fib(n−2). Why is it so slow, and how does memoization fix it?
- Naive fib(n) recomputes fib(n−2) twice, fib(n−3) three times, and so on — the calls branch exponentially, giving roughly O(2ⁿ).Nothing is remembered, so the same subproblems are solved again and again.
- Memoize: keep a cache; the first time fib(k) is computed, store it; every later call returns it instantly.Each of the n distinct subproblems is now solved exactly once.
- The work drops to O(n) — a fib(50) that would hang now returns immediately.n subproblems × O(1) each, thanks to the cache.
The naive version repeats subproblems exponentially (O(2ⁿ)); caching each of the n subproblems once turns it into O(n) — the essence of dynamic programming.