Three problems, one machine
You have now built every part of the dynamic-programming machine. You know what makes a problem suitable — optimal substructure plus overlapping subproblems — and you know the four steps of putting it to work: choose a state, write the transition, pick an evaluation order, and, if you need more than a number, reconstruct the actual solution. This guide is where that machine earns its keep. We run it on three problems that are not toys — they sit inside spell-checkers, version-control diffs, DNA aligners, and budget planners — and you will see the very same recipe produce three quite different answers.
Treat these three not as facts to memorize but as patterns to internalize. 0/1 knapsack is the canonical "pick a subset under a budget" problem; the longest common subsequence (LCS) and edit distance are the canonical "line up two sequences" problems. Almost every DP you ever design will rhyme with one of these. The skill to grow here is reading a new problem and hearing which classic it echoes — because once you hear it, the state and transition almost write themselves.
0/1 knapsack: choosing a subset under a budget
You have n items; item i has weight w_i and value v_i, and a sack that holds total weight at most W. Each item is taken whole or left behind — that "0 or 1" is the whole story. You want the most valuable subset that fits. Why not be greedy and grab the best value-per-weight first? Because that is exactly the trap from the greedy rung: for indivisible items the greedy rule can be arbitrarily bad, since you cannot shave a sliver to fill the leftover gap. So we reason over subproblems instead.
Here is the move that unlocks it — choosing the right state. Let dp[i][c] be the best total value using only the first i items with capacity exactly c available. The transition asks one yes/no question about item i: either we leave it (value dp[i-1][c]) or we take it, if it fits, gaining v_i but spending w_i of capacity (value v_i + dp[i-1][c - w_i]). The answer is the larger of the two. That single "take it or leave it" branch is the heartbeat of every subset DP.
dp[i][c] = max(
dp[i-1][c], # skip item i
v[i] + dp[i-1][c - w[i]] # take item i, only if w[i] <= c
)
# base: dp[0][c] = 0 for all c (no items -> no value)
# answer: dp[n][W]Because dp[i] depends only on dp[i-1], the natural evaluation order is i from 1 to n, c from 0 to W. The table has n*(W+1) cells and each costs O(1), so the running time is O(n*W). Pause on that W: it is the numeric value of the capacity, not its bit-length, so this is pseudo-polynomial, not truly polynomial — double the capacity and the work doubles, even though writing the number down only took one more digit. For modest W it is wonderfully fast; for an astronomically large W it is not, and that gap is no accident, because 0/1 knapsack is NP-hard and a genuinely polynomial exact algorithm is not known.
LCS: lining up two sequences
Now a different shape. Given two strings X and Y, the longest common subsequence is the longest sequence of characters appearing in both, in order but not necessarily contiguous. In "ABCBDAB" and "BDCAB", "BCAB" is a common subsequence of length 4. This is the engine behind file-diff tools: the lines two versions share, in order, are exactly their LCS, and everything else is an insertion or deletion. Subsequence, note, not substring — gaps are allowed, which is what makes brute force (try all 2^m subsequences of X) hopeless and DP essential.
Define the state by prefixes — the workhorse choice for sequence problems. Let dp[i][j] be the LCS length of the first i characters of X and the first j characters of Y. Look only at the last characters. If X[i] equals Y[j], that shared character can end an LCS, so dp[i][j] = 1 + dp[i-1][j-1]: match them and recurse on both shorter prefixes. If they differ, at least one of them is not in the LCS, so we drop one end and take the better: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). The base case is an empty prefix: dp[0][j] = dp[i][0] = 0.
Fill the table row by row, i from 1 to n and j from 1 to m; each cell looks only up and to the left, so by the time you reach a cell its three neighbors are ready. The cost is O(n*m) time and, if you only want the length, O(min(n,m)) space by keeping two rows. To recover the actual subsequence, walk backward from dp[n][m]: on a match step diagonally and emit the character; otherwise move toward whichever neighbor gave the maximum. Reverse what you collected and you have one optimal LCS.
Edit distance: LCS's wealthier cousin
Edit distance (the Levenshtein distance) asks: what is the minimum number of single-character edits — insert, delete, or substitute — that turns string X into string Y? "kitten" becomes "sitting" in three edits (substitute k->s, e->i, insert g). This is the math inside spell-checkers offering corrections and inside biological sequence alignment. It is LCS's cousin because both compare two prefixes and decide what to do with the last characters — but edit distance minimizes a cost instead of maximizing a length, and it carries a third move (substitution) that LCS lacks.
Same prefix state: let dp[i][j] be the edit distance between the first i characters of X and the first j of Y. The transition reads off the three edits directly. If X[i] = Y[j], the last characters already agree for free, so dp[i][j] = dp[i-1][j-1]. Otherwise we pay 1 and take the cheapest of three repairs: delete X[i] (dp[i-1][j]), insert Y[j] (dp[i][j-1]), or substitute (dp[i-1][j-1]). The base cases are not zero this time — they are the only place this differs from LCS in spirit: turning an i-character prefix into the empty string costs i deletions, so dp[i][0] = i and dp[0][j] = j.
- State: dp[i][j] = edit distance between X[1..i] and Y[1..j].
- Base cases: dp[i][0] = i and dp[0][j] = j (delete everything, or insert everything).
- Transition (match): if X[i] = Y[j], dp[i][j] = dp[i-1][j-1] — no cost.
- Transition (mismatch): else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
- Order: i then j, increasing; each cell needs its up, left, and up-left neighbors, all already filled.
The cost is O(n*m) time and O(n*m) space — or O(min(n,m)) space if you only need the number and roll two rows. To recover the actual sequence of edits, store no extra information: just retrace from dp[n][m] by checking which of the three (or the free match) produced each value, exactly the parent-pointer walk you learned for any tabulated DP. Notice how little changed from LCS — a different objective, one extra move, nonzero base cases — yet the four-step recipe is identical. That sameness is the real lesson of this rung.
What carries over, and what to watch
Step back and the family resemblance is striking. Knapsack indexes by (items used, capacity left) and branches on take-or-leave; LCS and edit distance index by (prefix of X, prefix of Y) and branch on what to do with the last characters. In all three the state is a tuple of progress counters, the transition is a small constant-size choice, and the table is filled so every dependency is ready before it is needed. When you next face an unfamiliar DP, ask first: what are my progress counters, and what is the small decision at each step? That is choosing the state and the transition — the two hard parts, the same two parts you drilled in the previous guide.
Three honest cautions before you reach for these. First, asymptotics describe scaling, not a verdict at every size: O(n*W) knapsack is splendid for small W but the W is a value, not a bit-count, so it is only pseudo-polynomial — a reminder that the same O(n*W) can be fast on one instance and hopeless on another. Second, these table sizes also fix your space, and the two-row trick that shrinks memory also throws away the path, so reconstruction needs the full table or a cleverer (Hirschberg-style) divide-and-conquer. Third, do not over-trust the pattern: matching last characters works because optimal substructure was proved for these objectives, and a superficially similar problem (say, longest common substring, which forbids gaps) needs a different recurrence. The recipe is a guide, never a substitute for checking that substructure actually holds.