Dynamic programming patterns

Dynamic programming (DP) solves a problem by combining the answers to smaller versions of it, and storing each answer so it is computed only once. It applies when the problem has

• optimal substructure: the best answer is built from the best answers to sub-problems, and
• overlapping sub-problems: the same sub-problems come up again and again.

Hints in the wording: "the number of ways", "the minimum cost", "the maximum value", "is it possible", over a sequence or grid. (The Python course's memoization lesson and the Algorithms course's DP lessons go further.)

The recipe

1. State: what does dp[i] mean, in words? ("the most money robbing houses 0 to i")
2. Recurrence: how does dp[i] come from smaller states?
3. Base cases: the smallest states, known directly.
4. Order: compute states so that each one's ingredients are ready (bottom-up), or recurse with a cache (top-down).
5. Answer: which state is it?

House robber

Houses in a row hold money; robbing two neighbours sets off the alarm. What is the most you can take?

State: best[i] = the most from houses 0..i. For house i, either skip it (best[i − 1]) or rob it (money[i] + best[i − 2]):

best[i] = max(best[i − 1], money[i] + best[i − 2])

def rob(money):
    before_previous, previous = 0, 0          # best[i - 2] and best[i - 1]
    for m in money:
        current = max(previous, m + before_previous)   # skip this house, or rob it
        before_previous, previous = previous, current
    return previous

print(rob([2, 7, 9, 3, 1]))
print(rob([5, 1, 1, 5]))

Each state needs only the two before it, so two variables replace the table: O(n) time and O(1) space.

Coin change

The fewest coins that make an amount, or −1 if impossible.

State: fewest[a] = the fewest coins for amount a. The last coin is some c, so fewest[a] = 1 + min(fewest[a − c]) over the coins c ≤ a. Base case: fewest[0] = 0. Amounts that cannot be made stay at infinity.

def coin_change(coins, amount):
    INF = float("inf")
    fewest = [0] + [INF] * amount            # fewest[a]: coins needed for amount a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and fewest[a - c] + 1 < fewest[a]:
                fewest[a] = fewest[a - c] + 1
    return fewest[amount] if fewest[amount] != INF else -1

print(coin_change([1, 3, 4], 6))
print(coin_change([2], 3))

O(amount × coins). The greedy "always take the biggest coin" fails for coins like [1, 3, 4] and amount 6: greedy takes 4 + 1 + 1 (3 coins), but 3 + 3 is 2. DP tries every last coin, so it cannot be fooled.

More patterns

In an interview, say the state and recurrence before coding. If the recurrence is right, the code is easy; if it is wrong, no amount of code will help.

Mark lesson complete