Dynamic Programming

No. 11 · SVG · Ledger1-D · 2-D · bottom-up · keep only what you need

Drag across the ledger. Click it, then use ← → to step and Space to play.

Dynamic programming is recursion whose subproblems overlap, solved once each. Plain recursion for climb_stairs(5) asks for climb_stairs(3) twice, climb_stairs(2) three times, and so on: an exponential pile of repeats (the call tree on page 3). DP turns it around: bottom-up, it fills a ledger from the smallest case up, so every answer it needs is already written down. And since each entry only reads the last one or two entries (or the row above), the rest can be forgotten: often just the last two values or the last row are kept.

FIG. 11 · A ledger of answers, filled in order. Red is the entry being computed; red-ringed entries are the ones it reads, with arrows showing the dependency. Hatched entries are base cases. Faded entries have been forgotten, because nothing will read them again; the black tags (one, two, row, new, rob1, rob2) are the only values the code still holds.

Step 1 / 1
READY
Work
Memory
Plain recursion
Result
Codeclimb_stairs
def climb_stairs(n):               # 1-D: ways(n) = ways(n-1) + ways(n-2)
    one, two = 1, 1                # keep only the last two answers
    for _ in range(n - 1):
        one, two = one + two, one
    return one

Examples

1-D DP · LeetCode 198

houses = [2, 7, 9, 3, 1], and you can't rob two neighbours. At each house: rob it plus the best from two back, or skip it and keep the best from one back. Two running numbers are enough. Answer: 12 (2 + 9 + 1). Trigger: "maximum", choices that repeat subproblems.

O(n) timeO(1) spaceone pass, two variables, instead of 2ⁿ subsets
2-D DP · LeetCode 1143

a = "abcde", b = "ace". dp[i][j] is the LCS of the first i letters of a and first j of b. Matching letters extend the diagonal; otherwise take the better of dropping one letter. Answer: 3 ("ace"). Trigger: "longest common subsequence".

O(m × n) timeO(m × n) spaceeach cell reads three neighbours; two rows suffice for just the length

Time and space

ShapeTimeSpaceWhy
1-D (climb stairs, house robber)O(n)O(1) with two variablesOne entry per position, each reading the previous one or two. Older entries are never read again.
2-D grid (unique paths)O(m × n)O(n) with one rowOne entry per cell, each reading up and left. Rows above the previous one are never read again.
2-D strings (LCS)O(m × n)O(m × n) full table, O(n) for length onlyKeep the whole table if you need to trace back the actual subsequence.
Plain recursion, no memoO(2ⁿ)O(n) stackEvery call branches and the branches overlap, so the same subproblem is solved again and again.

Top-down or bottom-up?

Top-down is the recursion plus a memo dict (page 3): it only solves the subproblems it actually reaches, and reads like the recurrence. Bottom-up is a loop that fills the table from the base cases: no recursion depth limit, and once you see which entries each step reads, you can shrink the table to the last row or the last two values. Same answers, same O(time); bottom-up usually wins on space.

How to spot the recurrence

Ask: what is the last choice? For stairs, the last move was 1 or 2 steps. For a grid, the robot arrived from above or from the left. For houses, the last house was robbed or skipped. Each option leaves a smaller version of the same problem, and the answer combines them with +, min or max.

Trigger words: when the problem wants DP

Counting and optimizing

  • number of ways
  • minimum cost
  • maximum cost
  • can you reach

Combine the answers of smaller cases with +, min, max or or.

Two sequences

  • longest common subsequence
  • edit distance

A 2-D table indexed by a prefix of each.

The tell is choices that repeat subproblems: if the recursion tree would ask the same question twice, store the answer.

Template

def climb_stairs(n):               # 1-D: ways(n) = ways(n-1) + ways(n-2)
    one, two = 1, 1                # keep only the last two answers
    for _ in range(n - 1):
        one, two = one + two, one
    return one

def unique_paths(m, n):            # 2-D: dp[r][c] = up + left
    row = [1] * n
    for _ in range(m - 1):
        new = [1] * n
        for c in range(1, n):
            new[c] = new[c - 1] + row[c]
        row = new
    return row[-1]