Dynamic Programming

Some problems are made of smaller copies of themselves, and the same smaller copies come up again and again. Solving each copy fresh every time it appears makes the work explode. Dynamic programming (DP) solves each one once and looks it up after that. It has a reputation for being hard, but most of that difficulty goes away with a fixed set of questions to ask before writing any code.

The worked example is the "house robber" problem, followed by a grid. The lab uses the same method on stairs, grid paths and the longest increasing subsequence.

The problem

A row of houses holds some money each. You may take from any houses you like, but never from two neighbours. What is the most you can take?

houses = [2, 7, 9, 3, 1]      # best: 2 + 9 + 1 = 12

The obvious approach: try everything

For the last house there are two choices: take it (and then the best from all houses before its neighbour) or skip it (and then the best from all houses before it). That gives a recursion:

calls = 0

def best_plain(houses, n):
    """Most money from the first n houses."""
    global calls
    calls += 1
    if n == 0:
        return 0
    if n == 1:
        return houses[0]
    return max(best_plain(houses, n - 1),                    # skip house n - 1
               houses[n - 1] + best_plain(houses, n - 2))    # take it

assert best_plain([2, 7, 9, 3, 1], 5) == 12
calls = 0
best_plain([1] * 25, 25)
assert calls > 200_000

It is correct and it is hopeless: 25 houses make over 200,000 calls, and each extra house multiplies the work by about 1.6. The reason is visible if you trace it: best_plain(houses, 23) is asked for by both n = 24 and n = 25, and each of those asks for smaller answers again. The same questions are answered over and over.

Remember each answer: memoization

Keep every answer the first time it is computed, and look it up after that:

def best_memo(houses):
    memo = {}
    def best(n):
        if n in memo:
            return memo[n]
        if n == 0:
            result = 0
        elif n == 1:
            result = houses[0]
        else:
            result = max(best(n - 1), houses[n - 1] + best(n - 2))
        memo[n] = result
        return result
    return best(len(houses))

assert best_memo([2, 7, 9, 3, 1]) == 12
assert best_memo([1] * 25) == 13

Now each n from 0 to the number of houses is computed once: O(n) time instead of exponential. The standard library can add the memo for you with functools.cache, once you have seen what it does.

Fill a table: tabulation

Memoization works top-down and lets recursion discover which answers it needs. A table works bottom-up: compute the small answers first, in an order where every entry only reads entries already filled.

def best_table(houses):
    best = [0] * (len(houses) + 1)            # best[n]: most money from the first n houses
    for n in range(1, len(houses) + 1):
        take = houses[n - 1] + (best[n - 2] if n >= 2 else 0)
        best[n] = max(best[n - 1], take)
    return best[len(houses)]

assert best_table([2, 7, 9, 3, 1]) == 12
assert best_table([]) == 0

No recursion, no memo dictionary, and the order of the loop is the proof that every best[n - 1] and best[n - 2] is ready when it is read. That is the DP invariant:

When an entry is filled, every entry it reads already holds its final answer.

The six questions

Every DP solution answers the same six questions. Write the answers down before the code, and the code mostly writes itself:

The last row is often forgotten. A table knows the best amount; the choices that produced it can be recovered by walking back through the table and asking which option each entry used:

def chosen_houses(houses):
    best = [0] * (len(houses) + 1)
    for n in range(1, len(houses) + 1):
        best[n] = max(best[n - 1], houses[n - 1] + (best[n - 2] if n >= 2 else 0))
    chosen = []
    n = len(houses)
    while n > 0:
        if best[n] == best[n - 1]:
            n -= 1                     # house n - 1 was skipped
        else:
            chosen.append(n - 1)       # house n - 1 was taken, so its neighbour was not
            n -= 2
    return chosen[::-1]

assert chosen_houses([2, 7, 9, 3, 1]) == [0, 2, 4]

The lab's longest increasing subsequence stores a previous table for the same purpose, so that walking back is a matter of following links.

Two dimensions

The state can need two numbers. The cheapest path from the top-left to the bottom-right of a grid of costs, moving only right or down:

def cheapest_path(grid):
    rows, cols = len(grid), len(grid[0])
    cost = [[0] * cols for _ in range(rows)]        # a new list for every row
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                cost[r][c] = grid[0][0]
            elif r == 0:
                cost[r][c] = cost[r][c - 1] + grid[r][c]
            elif c == 0:
                cost[r][c] = cost[r - 1][c] + grid[r][c]
            else:
                cost[r][c] = min(cost[r - 1][c], cost[r][c - 1]) + grid[r][c]
    return cost[rows - 1][cols - 1]

assert cheapest_path([[1, 3, 1],
                      [1, 5, 1],
                      [4, 2, 1]]) == 7

Row by row, left to right, is an order in which the cell above and the cell to the left are always ready. Note the table's construction: [[0] * cols] * rows would repeat one row list rows times, and writing one cell would write it in every row. That bug (you met it in Module 6) silently corrupts every answer in a DP table.

What it costs

A DP's cost is number of states × work per state. House robber: n states, constant work each, O(n) time and O(n) space. The grid: rows × cols states, constant work each. When an entry only reads the previous one or two, the table can shrink to a couple of variables, O(1) space — but write the full table first and optimize once it is correct.

Where it goes wrong

• No clear state. If you cannot say in one sentence what best[i] means, the rule will not come out right.
• Wrong order. Reading an entry before it is filled gives a silent wrong answer, not an error.
• Greedy instead of DP. Taking the locally best choice (the richest house, the biggest coin) is often wrong; DP compares every option at each state.
• Shared rows. [[0] * cols] * rows repeats one list.
• Forgetting reconstruction. Many problems ask for the path or the chosen items, not just the number.

In the lab

The lab counts the calls a plain recursion makes for climbing stairs and watches a memo collapse them, fills a table of grid paths cell by cell (after fixing a shared-row bug), and builds the two tables for the longest increasing subsequence before walking back along them to recover it; an optional stretch finds the length in O(n log n) with binary search. The mastery challenge is a new optimization problem that names no technique, with questions for each part of the six-question plan above.