The recurrence was the hard part all along
The previous three guides taught the machinery. You saw that a plain recursion can repeat the same work exponentially, you wrapped it in a cache to get top-down memoization, and you turned the same recurrence into loops with bottom-up tabulation. But notice that all three guides quietly handed you the recurrence. They never said where it came from. That is the gap this guide closes: every dynamic program lives or dies on a recurrence you must invent, and inventing it is two decisions — what a subproblem is (the state) and how subproblems connect (the transition).
Here is the reassuring news and the warning, together. Once the state is chosen well, the transition usually writes itself and the memoization-or-tabulation choice is just an engineering detail. But if the state is wrong, no amount of clever coding rescues you — you will compute fast, confident, wrong answers. So the real skill of dynamic programming is not coding the table; it is the design step that happens before any code, on paper. Think of a state as the precise question that one table cell answers, and the transition as the sentence that builds that answer out of smaller answers.
The state: a name for one subproblem
Defining the state means choosing a small bundle of values that pins down exactly one subproblem and serves as the key into your table. A good state is judged on two axes that pull against each other. It must be sufficient: it has to capture everything about the situation that affects the future, so the best continuation depends only on the state and never on hidden history. And it should be minimal: it carries no detail the future ignores, because every extra dimension multiplies the number of states — and the number of states is the number of cells you must fill.
The test for sufficiency is concrete: stand at a half-finished solution, look only at the state, and ask whether you have enough to make the next choice optimally. If you find yourself reaching for a fact the state did not record — which earlier items you took, what the running parity was — then the state is under-specified, distinct subproblems are colliding in one cell, and the answers will be wrong. The cure is never to smuggle that fact in through side data; it is to widen the state until it records what the future needs. For the longest increasing subsequence, the weak state 'first i elements' fails because the transition cannot tell whether element i can extend a subsequence; the fix is dp[i] = the longest increasing subsequence ending exactly at index i, which fixes the last element and makes the future depend only on the state.
The transition: how states connect
Once you know what a state is, the transition is the rule that computes one state's answer from the answers of smaller states. If states are the nouns you store, the transition is the verb that links them. It almost always has the same shape: to solve this state, enumerate every possible first choice, solve the residual subproblem each choice leaves behind, and combine — take the max, the min, the sum, or the count, depending on what you are optimizing. Writing the transition correctly is exactly writing the recurrence, and its correctness rests on optimal substructure: each branch you reference must itself be an optimal sub-answer, or the whole thing is wrong.
The 0/1 knapsack is the cleanest illustration of the 'first choice' shape. With state dp[i][w] = the best value using the first i items under capacity w, the only choice for item i is take it or leave it, and the transition reads that choice off directly. Say the recurrence aloud and it tells its own story: the best you can do with the first i items is the better of ignoring item i (so you still have all w available for the first i-1 items) and taking it (gaining its value but spending its weight, leaving w - weight[i] for the rest). Each branch is an optimal answer to a strictly smaller state — substructure made concrete.
dp[i][w] = max( dp[i-1][w], # leave item i
value[i] + dp[i-1][w - weight[i]] ) # take item i (needs weight[i] <= w)
# state count * work-per-state = running time
# knapsack: O(nW) states * O(1) work = O(nW)
# LIS (loop over predecessors): O(n) states * O(n) work = O(n^2)The transition also fixes the cost of your DP, and this is worth internalizing as a formula: running time = (number of distinct states) times (work to evaluate one transition). A knapsack transition does O(1) work over O(nW) states, so O(nW). The longest-increasing-subsequence transition loops over O(n) predecessors per state across n states, so O(n^2). This single product is how you predict a DP's complexity before writing a line — and it is why shrinking the state pays off twice, once in memory and once in time.
Base cases and the order you fill them
A transition builds bigger states from smaller ones, but you cannot build forever — you eventually hit the smallest states with nothing beneath them. Those are the base cases, and you fill them in by hand, directly from the meaning of the problem, before any loop or recursion runs. They are the foundation the whole table rests on; if a base case is wrong, every value computed above it silently inherits the error. They look trivial and are exactly where the most common bugs hide. For an empty input the answer might be 0 (the LCS with an empty string is empty), or i (turning a length-i string into the empty string costs i deletions), or 1 (there is exactly one way to do nothing, in a counting DP).
Base cases also encode the boundary of feasibility. When some situations are impossible, you seed them with a sentinel — positive infinity for a minimization, negative infinity for a maximization — so that the 'best' operation automatically steps around them. Coin change is the classic: dp[0] = 0 (zero coins make amount zero) while every positive amount starts at infinity, so an amount that genuinely cannot be formed stays infinite and is never mistaken for achievable. Seed with 0 instead of infinity and impossible states masquerade as free, poisoning everything above. A wrong sentinel or an off-by-one at the boundary is the bug that hides best, because the bulk of the table looks perfectly reasonable.
Now you need an order to fill the cells, and there is one rule you may never break: before you compute a cell, every cell it depends on must already hold its final value. The evaluation order is any sequence that respects this. Picture each state as a node, with an arrow from X to Y whenever computing X needs Y; a valid fill order is any topological order of that dependency graph. For one-dimensional DPs where dp[i] needs smaller indices, just increase i. For grid DPs where dp[i][j] reads up, left, and up-left, fill rows top-to-bottom and within each row left-to-right. For interval DPs, increase the interval length so all shorter intervals are ready first. You read the order straight off the transition.
Reading the answer back out
A filled table tells you the value of the optimum — the best knapsack value, the LCS length, the minimum edit cost. But often you want the optimum itself: which items to pack, which letters align, which edits to apply. That is reconstructing the solution, and the value alone does not hand it to you. The standard trick is to walk the table backward from the final cell, and at each step ask which branch of the transition actually achieved the stored optimum. The branch you took tells you the choice you made; you follow it to the state it came from and repeat until you reach a base case.
- Start at the cell holding the final answer — for 0/1 knapsack, dp[n][W].
- Ask which transition branch produced this value. If dp[i][w] equals dp[i-1][w], item i was left out; otherwise it was taken.
- Record the choice (e.g. 'took item i') and move to the predecessor state that branch came from.
- Repeat until you hit a base case; the recorded choices, reversed, are the optimal solution.
Re-deriving the chosen branch by comparison works, but a cleaner and faster habit is parent-pointer backtracking: at the moment you fill each cell and pick the winning branch, store a back-pointer to the predecessor it chose. Then reconstruction is just chasing pointers from the final cell to a base case — no re-checking the transition, no risk of breaking ties differently on the way back. The cost is one extra array of the same size as the table, a worthwhile trade whenever you need the witness and not merely its score.
The five-question recipe
Put it together and every DP you will ever write answers the same five questions, in this order. What is the state — the minimal sufficient name for a subproblem? What is the transition — how does each state's answer come from smaller states, by enumerating a first choice? What are the base cases — the smallest states, filled in by hand, with the right sentinels? What is the evaluation order — a topological order of the dependency graph (or just recurse and memoize, letting the stack find one)? And finally, do you need to reconstruct the solution, or is the value enough?
Two honest reminders before the next guide turns these into full worked examples. First, this whole recipe only produces a correct program if the problem actually has optimal substructure — that a transition 'looks right' is never a proof, and a recurrence that references subproblems which secretly interfere (sharing a resource the state does not track) is wrong however plausible it reads. Second, the recipe predicts cost but does not guarantee a good cost: states times work-per-state can still be exponential if your state needs an exponential number of values, which is exactly what happens when a problem genuinely seems to need a subset as part of its state. Dynamic programming is a design discipline, not a magic wand.