Dynamic Programming
Recognising overlapping subproblems, and turning exponential recursion into linear time
Dynamic programming has a reputation for being hard, but the core idea is small: compute each subproblem once and remember the answer.
Everything else — memoization, tabulation, space optimisation — is bookkeeping around that one sentence.
Seeing the Waste
The name is unhelpful — it means nothing, and it was chosen to sound impressive. Ignore it. Here is what is actually going on.
Take "how many ways can I climb 5 stairs, taking 1 or 2 at a time?" To reach step 5 you arrived from either step 4 or step 3. So:
ways(5) = ways(4) + ways(3)Write that as plain recursion and it is correct. It is also catastrophically slow — and the reason is visible the moment you draw it.
How bad the waste gets
The tree roughly doubles in width at every level, so plain recursion is O(2ⁿ). Remembering answers means each distinct subproblem runs once, so it becomes O(n).
n = 40 recursion: ~1,000,000,000 calls → many seconds
with a cache: 40 calls → instant
n = 60 recursion: ~10¹⁸ calls → ~30 years
with a cache: 60 calls → instantThis is not an optimisation. It is the difference between a program that finishes and one that does not.
The test for DP, in one question
Am I computing the same thing more than once?
If yes, and the problem asks for a count, a minimum, a maximum, or a yes/no — write down what you compute. That is dynamic programming. There is nothing else to it conceptually; the rest of this page is about where to write things down.
When Does DP Apply?
Two properties must both hold.
1. Optimal substructure
The answer for a problem can be built from answers to smaller versions of the same problem.
"The number of ways to climb 5 stairs = ways to climb 4 + ways to climb 3."
2. Overlapping subproblems
The same smaller problems come up again and again.
This is what separates DP from divide-and-conquer. Merge sort has optimal substructure, but its halves never overlap — caching would buy nothing. In Climbing Stairs, f(3) is recomputed exponentially many times without a cache.
The Four Stages
Most DP solutions pass through these, and you can stop at whichever is good enough.
1. Naive recursion — O(2ⁿ)
Write the recurrence directly. Correct, unusably slow, and the right place to start because it forces you to state the recurrence precisely.
2. Memoization (top-down) — O(n)
Keep the recursion, add a cache. In Python, @lru_cache does it in one line. The shape of your thinking stays intact.
Memoization is just "write the answer on a notepad before returning it, and check the notepad first". The odd spelling — no r — comes from memo.
3. Tabulation (bottom-up) — O(n)
Replace recursion with a loop that fills a table from the base cases upward. No stack-overflow risk, and usually a constant-factor faster.
Top-down and bottom-up are the same answers in a different order
TOP-DOWN (memoization) BOTTOM-UP (tabulation)
start at the question start at the base cases
ways(5) needs ways(4)… ways(1)=1, ways(2)=2
…which needs ways(3)… ways(3) = 2+1 = 3
…which hits the base ways(4) = 3+2 = 5
then unwinds back up ways(5) = 5+3 = 8| Top-down | Bottom-up | |
|---|---|---|
| Written as | Recursion + cache | A loop filling an array |
| Computes | Only subproblems it actually needs | All of them, in order |
| Risk | Stack overflow when deep | None |
| Easier to | Write — it mirrors the recurrence | Optimise — the table is right there |
Start top-down, because it is a direct translation of the recurrence you already wrote. Convert to bottom-up when depth becomes a risk or you want to shrink the memory.
4. Space optimisation — often O(1)
If the recurrence only looks back a fixed number of steps, the table collapses into that many variables.
ways(n) only ever needs ways(n-1) and ways(n-2). Everything older is dead weight — so keep two variables and let the rest go.
Full table: [1, 2, 3, 5, 8, 13] O(n) memory, most of it never read again
Two variables: prev=8, curr=13 O(1) memory, same answersThis is why several problems on this site are dynamic programming without ever looking like it. Best Time to Buy and Sell Stock is a DP table squeezed down to one running minimum.
Climbing Stairs, n = 6:
Naive recursion: ~25 calls, doubling with n
Memoized: 6 computations, O(n) space
Tabulated: 6 iterations, O(n) space
Two variables: 6 iterations, O(1) space ← f(n) needs only f(n-1), f(n-2)Recognising DP in the Wild
| The problem asks for… | Likely DP |
|---|---|
| "how many ways to…" | counting DP |
| "minimum / maximum cost to…" | optimisation DP |
| "can you reach / partition…" | boolean DP |
| "longest / shortest subsequence" | sequence DP |
Not every DP-shaped problem needs DP
Jump Game has a textbook O(n²) DP solution — and an O(n) greedy one. Best Time to Buy and Sell Stock is DP with the table collapsed to two variables, at which point calling it DP is optional.
When a greedy choice is provably safe, take it. DP is the fallback for when it is not.
All Problems
| Problem | Difficulty | Recurrence |
|---|---|---|
| Climbing Stairs | Easy | f(n) = f(n-1) + f(n-2) |
| Min Cost Climbing Stairs | Easy | f(i) = cost[i] + min(f(i-1), f(i-2)) |
| House Robber | Medium | f(i) = max(f(i-1), f(i-2) + nums[i]) |
| Coin Change | Medium | f(a) = 1 + min(f(a - c)) over coins c |
| Longest Increasing Subsequence | Medium | f(i) = 1 + max(f(j)) where nums[j] < nums[i] |
| Unique Paths | Medium | f(r,c) = f(r-1,c) + f(r,c-1) |
| Longest Common Subsequence | Medium | f(i,j) = f(i-1,j-1)+1 or max(f(i-1,j), f(i,j-1)) |
| Word Break | Medium | ok(i) = any(ok(j) and s[j:i] in words) |
One dimension or two
| Recurrence looks back at | Table | Examples |
|---|---|---|
| Earlier positions in one sequence | 1-D array | Climbing Stairs, House Robber, Coin Change |
| Prefixes of two sequences, or a grid | 2-D table | Unique Paths, Longest Common Subsequence |
The tell is in the problem statement. Two inputs to compare, or a grid to cross, almost always means two dimensions — because the subproblem needs a position in each.
Related Elsewhere
- Best Time to Buy and Sell Stock — DP compressed into a running minimum
- Jump Game — where greedy beats the DP formulation
- Trapping Rain Water — has a classic prefix/suffix DP solution alongside the two-pointer one