Dynamic programming: finding the recurrence

Dynamic programming has a reputation for being hard, and the reputation is earned by how it is taught rather than by the technique. Almost every explanation opens with a finished recurrence — here is the formula, now fill in the table — as though the formula had been obvious. It was not obvious. Producing it was the entire difficulty, and that step is exactly the one that gets skipped.

So this is about finding the recurrence. The tables and loops at the end are mechanical once you have it, and there is a repeatable procedure for getting there.

The procedure

Six steps, applied in this order every time. The discipline is in resisting the urge to jump to step five.

1. Write the brute-force recursion. No cleverness. Express the answer in terms of the same question asked about something smaller.
2. Name the state. The smallest set of variables that fully determines a subproblem's answer.
3. Check that subproblems repeat. If the same state recurs, caching pays. If it never does, this is not a dynamic programming problem.
4. Add memoisation. Cache by state. This is top-down dynamic programming, and it is usually where you should stop.
5. Convert to bottom-up only if you need to — recursion depth, or to enable the next step.
6. Reduce space if only the last row or two of the table are ever read.

Steps one and two are the work. Step four is three lines. Most of the difficulty people attribute to dynamic programming is really the difficulty of step two.

The two conditions, and one that fails

Overlapping subproblems means the same question comes up repeatedly during the recursion. That is what makes a cache worth having — without repeats, you are storing answers you will never look up again.

Optimal substructure means an optimal solution is built from optimal solutions to subproblems. This one deserves scepticism rather than recitation, because it does not always hold.

A case where it fails: the longest simple path between two nodes in a graph with cycles. It seems to decompose — the longest path from A to C ought to be the longest from A to B plus the longest from B to C. It does not work, because "simple" means no repeated nodes, and the two optimal halves may both use the same node. Splicing them produces something that is not a valid path at all. The subproblems interfere with each other, so their optimal answers cannot be combined, and dynamic programming does not apply. That the problem looks decomposable is what makes it instructive.

Working the procedure: counting ways up a staircase

You can climb one or two steps at a time. How many distinct ways to reach step n?

Step one, the brute force. To be standing on step n you arrived from n-1 or from n-2. So the ways to reach n is the sum of the ways to reach each of those. That sentence is the recursion, and writing the sentence before the code is the habit worth building:

def stairs_naive(n):    if n <= 2:        return max(n, 1)          # 0 -> 1, 1 -> 1, 2 -> 2    return stairs_naive(n - 1) + stairs_naive(n - 2)

Step two, the state. One variable: which step you are on. Nothing else about the history matters — how you got to step 7 has no bearing on how many ways lead onward from it. That independence is what makes the state just n.

Step three, do subproblems repeat? Computing stairs_naive(30) asks for 29 and 28; 29 asks for 28 and 27. So 28 is computed twice, and each of those recomputes its whole subtree. Counting the calls makes "exponential" concrete:

  n= 10  ways=      89  calls=       109  n= 20  ways=  10,946  calls=    13,529  n= 30  ways=1,346,269  calls= 1,664,079

One and a half million function calls to answer a question about thirty steps. Ten more steps multiplies that by roughly another factor of seventeen. There are only thirty distinct subproblems here — the other 1.66 million calls are recomputation.

Step four, memoise. Cache by state:

def stairs_memo(n, memo=None):    if memo is None:        memo = {}    if n <= 2:        return max(n, 1)    if n in memo:        return memo[n]    memo[n] = stairs_memo(n - 1, memo) + stairs_memo(n - 2, memo)    return memo[n]

Each of the n states is computed once, so this is O(n) time and O(n) space. The 1.66 million calls become thirty. Nothing about the logic changed — only that answers are remembered.

Steps five and six. Bottom-up removes the recursion, and noticing that each answer needs only the previous two removes the table entirely:

def stairs_bottom_up(n):    if n <= 2:        return max(n, 1)    a, b = 1, 2                   # ways to reach steps 1 and 2    for _ in range(3, n + 1):        a, b = b, a + b    return b                      # O(n) time, O(1) space

All three agree, and the iterative version handles inputs the recursive one cannot reach without exhausting the stack:

  n= 30  memo=             1,346,269  bottom_up=             1,346,269  n= 90  memo= 4,660,046,610,375,530,309  bottom_up= 4,660,046,610,375,530,309

When greedy is wrong: fewest coins

Given coin denominations and a target, use the fewest coins. The obvious approach takes the largest coin that fits, repeatedly. It is fast, intuitive, and wrong.

With coins of 1, 7 and 10 and a target of 14, greedy takes a 10, then cannot use 7, so it fills with four 1s: five coins. Two 7s is the answer. Greedy failed because taking the largest coin now made the remaining subproblem worse, and it has no way to reconsider.

  coins=[1, 7, 10]     target= 14  greedy=5     dp=2  coins=[1, 3, 4]      target=  6  greedy=3     dp=2  coins=[1, 5, 10, 25] target= 30  greedy=2     dp=2  coins=[2]            target=  3  greedy=None  dp=None

The third line is why this mistake survives so long: on the coin system in your pocket, greedy is optimal, so it passes every test you would think to write. Denominations are chosen to make it so. Change the denominations and it silently returns wrong answers.

Running the procedure instead. Brute force: to make an amount, try each coin, and the answer is one plus the best way to make the remainder. State: the amount remaining — a single number, because how you got there does not constrain what follows. Subproblems repeat heavily, since many coin sequences reach the same remainder. Bottom-up:

def coin_dp(coins, target):    INF = float("inf")    best = [0] + [INF] * target        # best[0] = 0 coins for amount 0    for amount in range(1, target + 1):        for c in coins:            if c <= amount and best[amount - c] + 1 < best[amount]:                best[amount] = best[amount - c] + 1    return None if best[target] == INF else best[target]

Two details are doing real work. INF represents "unreachable", which is how the impossible case falls out naturally — with only 2-coins, no combination makes 3, so the entry stays infinite and the function returns None rather than a wrong number. And the loops are ordered so that best[amount - c] is always already final when it is read, which is the bottom-up invariant: never read an entry you have not finished computing.

Two dimensions, and reading the answer back

When one variable cannot capture a subproblem, the state grows. For the longest common subsequence of two strings, you need positions in both, so the state is a pair and the table is a grid.

The recurrence follows from a single question at each cell — do these two characters match? If they do, both strings advance and the length grows by one. If not, take the better of advancing either one:

def lcs(a, b):    n, m = len(a), len(b)    T = [[0] * (m + 1) for _ in range(n + 1)]    for i in range(1, n + 1):        for j in range(1, m + 1):            if a[i-1] == b[j-1]:                T[i][j] = T[i-1][j-1] + 1            else:                T[i][j] = max(T[i-1][j], T[i][j-1])    return T[n][m]

That gives the length. Usually you want the subsequence itself, which means walking back through the table, retracing the decisions that produced each cell:

    out, i, j = [], n, m    while i > 0 and j > 0:        if a[i-1] == b[j-1]:            out.append(a[i-1])        # this character was a match            i -= 1            j -= 1        elif T[i-1][j] >= T[i][j-1]:            i -= 1                    # we came from above        else:            j -= 1                    # we came from the left    return T[n][m], "".join(reversed(out))

  'ABCBDAB'  'BDCABA'   -> (4, 'BCBA')  'abc'      'abc'      -> (3, 'abc')  'abc'      'xyz'      -> (0, '')  ''         'abc'      -> (0, '')

The extra row and column of zeros are not decoration — they are the base case, encoding that the longest common subsequence with an empty string is empty. Handling it in the table rather than with special cases in the loop is why the loop body has no boundary checks in it.

The bugs that will cost you an evening

Three, and they share a symptom: the answer is right on the small example and wrong on the real input.

A base case that is off by one. Everything is built on the base case, so an error there propagates into every cell without ever looking like an error. Verify the smallest inputs by hand — n of 0, n of 1, an empty string — before trusting anything larger.

A state missing a variable. The subtlest failure. If your state does not fully determine the subproblem, two genuinely different situations share a cache entry, and the cache returns an answer computed for the other one. The tell is a solution that works until a case where some constraint you did not encode starts to matter. Test by asking: given only these variables, is the answer determined? If you need to know anything else — how many items are left, what you have already spent — that belongs in the state.

Iterating in the wrong order. Bottom-up requires every dependency to be computed before it is read. Get the loop order wrong and you read a zero that has not been filled in yet, producing a plausible, wrong, and entirely silent result. When in doubt, write the memoised version instead: recursion computes dependencies on demand, so the ordering problem cannot arise.

That last point is worth generalising. Top-down memoisation is easier to get right, easier to debug, and usually fast enough. Convert to bottom-up when you have a reason — depth limits, or a space optimisation you actually need — not as a matter of course.

Recognising one, and telling it apart from greedy

Wording that suggests dynamic programming: count the number of ways, find the minimum or maximum over a sequence of choices, is a target achievable, longest or shortest satisfying some condition. Structurally, you are making a decision at each step where the choices interact, and an early decision changes what remains available.

Wording that suggests greedy: the locally best choice is provably also globally best. Scheduling by earliest finishing time, or building a minimum spanning tree, work greedily because that property has been proven for them.

When you cannot tell, the fastest discriminator is to look for a counterexample to greedy, the way the 1-7-10 coins broke it above. Find one and the question is settled. Fail to find one after genuine effort and greedy is probably right — but note the asymmetry: a counterexample is proof, while failing to find one is only evidence. If correctness matters and you are unsure, dynamic programming is the choice that cannot be wrong for the reason greedy is wrong.