What DP actually is
Derive a DP from a brute force in three steps, name the state as the variables the future depends on, and state the cost as states times work per state.
Dynamic programming is recursion with the answers written down. A brute force that solves the same subproblem forty times becomes a DP the moment you store each answer the first time you compute it. The tables, the loop orders and the names are bookkeeping on top of that one idea.
The subject gets its reputation from being taught backwards — table first, recurrence pulled out of the air. Derived forwards, from a recursion you already know how to write, there is nothing new in it.
The two preconditions
Optimal substructure. The best answer to the whole is assembled from best answers to smaller instances of the same problem. If the cheapest way to make 11 from coins starts with a 5, the rest of that answer has to be the cheapest way to make 6 — otherwise you could substitute the cheaper way to make 6 and improve a solution that was supposed to be optimal.
Overlapping subproblems. The same smaller instance is asked for more than once. This is the part a cache is paid for.
People check the first and assume the second. Merge sort is the counterexample worth carrying: it has textbook optimal substructure — a sorted whole is built from two sorted halves — and every recursive call receives a distinct slice of the array. Nothing repeats, so a memo would run at a 100% miss rate and buy you a dictionary's worth of memory and hashing for nothing. Divide and conquer needs only the first precondition. Overlap is what turns it into DP.
One example, three shapes
Count the ways to climb n stairs taking one or two steps at a time. The last
move was either a single step from n-1 or a double from n-2, and those two
sets of paths do not intersect, so they add:
def ways(n): # brute force
if n <= 1:
return 1
return ways(n - 1) + ways(n - 2)
The call tree for ways(n) has 2 * ways(n) - 1 nodes. At n = 40 that is
2 x 165,580,141 - 1, about 331 million calls, for a function with 41 possible
inputs. At the roughly 10^8 simple operations per second used in
complexity by counting,
that is seconds of pure repetition — and far worse in Python, where a call costs
more than an arithmetic operation.
Write the answers down as you go and the repeats disappear:
def ways(n): # top-down, memoised
memo = {}
def go(k):
if k <= 1:
return 1
if k not in memo:
memo[k] = go(k - 1) + go(k - 2)
return memo[k]
return go(n)
Every distinct input is computed once, so there are 41 real evaluations instead of 331 million. Turn the recursion inside out and you get the table:
def ways(n): # bottom-up
dp = [1, 1] + [0] * (n - 1) # the two base cases, then room for the rest
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
Same numbers, same dependency order, no call stack. Since dp[i] reads only
the two cells behind it, the array collapses to two variables — that trick is
worked through in linear DP.
The three programs are the same computation. What changes is who decides the order: the recursion discovers it, the loop asserts it.
Naming the state
The state is the smallest set of variables that makes the future independent of the past. Two partial solutions belong to the same state when everything you can still do from them is identical — if that is true, you may keep the better one and discard the other, and that discard is where the exponential goes.
The test is a question: if I hand you only these variables, can you finish the
problem? Robbing houses along a street needs only the index i, because the
best you can do from i onward depends on nothing behind you. Add "you may rob
at most k houses" and the index is no longer enough — two paths reaching house
i with different counts have different futures — so the state becomes
(i, k) and the table gains a dimension.
Missing a variable is the failure that produces a DP which is fast and wrong. When two different histories reach the same state and disagree about what is still possible, the state is incomplete.
Complexity is states times work per state
That product is enough to size a solution before writing it:
| Shape | States | Work each | Total |
|---|---|---|---|
| Linear over an array | n | O(1) | O(n) |
| Two sequences | n x m | O(1) | O(n x m) |
| Item and capacity | n x C | O(1) | O(n x C) |
| Interval with a split | n^2 | O(n) | O(n^3) |
| Subset of n things | 2^n | O(n) | O(2^n x n) |
Space is the number of states you have to keep alive at once, which is often far fewer than the number you visit. Two sequences at n = m = 5,000 is 25 million cells — 200 MB as 8-byte integers, and fine as two rows of 5,000.
Top-down or bottom-up
Top-down is faster to write, matches the recurrence line for line, and visits only the states reachable from the answer — which matters when the table is sparse. It pays for a call stack: Python stops at about 1,000 frames, so a chain of 10^5 states has to be flattened. Bottom-up makes you state the order explicitly, and gives back the rolling-array saving and no depth limit. Write the memo first; convert when depth or space forces it.
In an interview
Say the five lines before you write code: state, transition, base case, order,
answer. "State is dp[i] = the best total using the first i houses. Transition
is rob i or skip it. Base cases are dp[0] and dp[1]. Order is increasing i.
The answer is dp[n]." That specification is most of the grade; the code after
it is transcription.
Then give the cost as a product — "n times C states, constant work each, so O(n x C) time and O(C) space after rolling the rows" — because that is the phrasing that shows you know why it is that fast rather than having memorised the figure.
The mistake that loses points: starting with the table. A candidate who writes loops before defining what a cell means cannot answer "why is that the recurrence?", and cannot debug it either. Follow the route in the solving loop: brute force, name the repetition, then cache it.
Check yourself
Merge sort has optimal substructure. Why does memoising it gain nothing?
Because no subproblem repeats — each call owns a distinct slice, so the cache never hits. DP needs overlap as well as substructure; without overlap you have plain divide and conquer, and the memo is pure overhead.
A DP has states (item, capacity) with 100 items and capacity 10,000, and a
constant-work transition. How many operations, and how much memory as one row of
64-bit integers?
100 x 10,001 is about 10^6 operations, well under a second. One row is 10,001 x 8 bytes, roughly 80 KB — the full table would be 8 MB, which is why rolling a single row is the default.
Your memoised recursion is correct on small inputs and dies at n = 10^5. What happened, and what is the fix?
The recursion depth exceeded Python's ~1,000-frame limit. Rewrite it bottom-up: the memo already tells you the state space, and the loop order is whatever direction makes the dependencies already computed.