Writing the recurrence, and checking it

Lesson · 12 min read · Dynamic programming · The recurrence

A recurrence says how a state's answer comes from the answers of the states its choices lead to. Two checks catch most wrong ones before any code is written.

The shape of every recurrence

With the state fixed, the recurrence lists the choices available at a state, what each choice contributes, and which state it leads to, then combines the options:

dp(s) = opt over choices a of [ contribution(s, a) ⊕ dp(next(s, a)) ]

This is Bellman's optimality equation. Only two operators change between problems:

Question	opt (over choices)	⊕ (along a choice)	Example
smallest cost	min	+	fewest coins, edit distance
largest value	max	+	knapsack, longest subsequence
how many ways	sum	×, or just the count	paths in a grid, ways to make change
is it possible	or	and	subset sum, word break

Writing it in this form, rather than straight into code, makes the next two checks easy.

Check 1: every solution is reachable

Take a solution you know is valid and follow its decisions through the recurrence. At every state, the decision it makes must be one of the choices the recurrence offers. If a valid solution has no path, the recurrence is missing a choice and will return something worse than the true optimum, or too small a count.

Typical miss: in edit distance, forgetting that a character can be kept for free when both strings agree, so the recurrence only ever pays.

Check 2 (for counting): every solution is counted once

For a count, each valid solution must correspond to exactly one path through the recurrence. Count the ways to pay 5 with coins 1, 2 and 5. The natural first attempt, ways(a) = Σ ways(a − c) over the coins, counts 1 + 2 + 2 and 2 + 1 + 2 and 2 + 2 + 1 separately: it counts sequences of coins, and gives 9. But a payment is a set of coins, and there are only 4: 5, 2 + 2 + 1, 2 + 1 + 1 + 1, and 1 + 1 + 1 + 1 + 1.

The fix is to make each combination reachable in one way only: decide the coins in a fixed order. The state becomes (i, a): ways to pay a using only the first i coin types. At each state, either use no more of coin i (go to i − 1) or use one more (stay at i, pay less):

ways(i, a) = ways(i − 1, a) + ways(i, a − coin[i])

ways(i, a) for coins 1, 2, 5 and amounts 0 to 5. Row "≤2" means coins 1 and 2 only.

Step 1 / 19

Base cases filled first.
Step 2 / 19

Pay 0 with coins up to 1: 1 way without another 1: 1.
Step 3 / 19

Pay 1 with coins up to 1: 0 ways without another 1, plus 1 using one more 1: 1.
Step 4 / 19

Pay 2 with coins up to 1: 0 ways without another 1, plus 1 using one more 1: 1.
Step 5 / 19

Pay 3 with coins up to 1: 0 ways without another 1, plus 1 using one more 1: 1.
Step 6 / 19

Pay 4 with coins up to 1: 0 ways without another 1, plus 1 using one more 1: 1.
Step 7 / 19

Pay 5 with coins up to 1: 0 ways without another 1, plus 1 using one more 1: 1.
Step 8 / 19

Pay 0 with coins up to 2: 1 way without another 2: 1.
Step 9 / 19

Pay 1 with coins up to 2: 1 way without another 2: 1.
Step 10 / 19

Pay 2 with coins up to 2: 1 way without another 2, plus 1 using one more 2: 2.
Step 11 / 19

Pay 3 with coins up to 2: 1 way without another 2, plus 1 using one more 2: 2.
Step 12 / 19

Pay 4 with coins up to 2: 1 way without another 2, plus 2 using one more 2: 3.
Step 13 / 19

Pay 5 with coins up to 2: 1 way without another 2, plus 2 using one more 2: 3.
Step 14 / 19

Pay 0 with coins up to 5: 1 way without another 5: 1.
Step 15 / 19

Pay 1 with coins up to 5: 1 way without another 5: 1.
Step 16 / 19

Pay 2 with coins up to 5: 2 ways without another 5: 2.
Step 17 / 19

Pay 3 with coins up to 5: 2 ways without another 5: 2.
Step 18 / 19

Pay 4 with coins up to 5: 3 ways without another 5: 3.
Step 19 / 19

Pay 5 with coins up to 5: 3 ways without another 5, plus 1 using one more 5: 4. Four ways to pay 5, each counted once.

Three more quick checks

Progress: every choice leads to a strictly smaller state, so the recursion ends and an order of computation exists.
Units: the contribution matches the question (counting adds counts, optimising adds costs).
A tiny example by hand: two or three elements, computed from the recurrence and from common sense. They must agree.

Most wrong DP answers in interviews come from recurrences that were never checked against one small example. It takes thirty seconds and is the best-spent time in the problem.