2-D dynamic programming

When to reach for it

• Paths through a grid that move in limited directions, counting them or finding the cheapest.
• Comparing two sequences: the longest shared run, the fewest edits, whether one interleaves with another.
• Choosing items under a capacity: each item either used or not, with a budget left over.
• Intervals of one sequence, where the answer for a range depends on smaller ranges inside it.

The core idea

Define dp[i][j] in words first. For two strings it is usually the answer for the first i characters of one and the first j of the other; for a grid, the answer for reaching cell (i, j). The recurrence then looks at a few neighboring cells, typically dp[i - 1][j], dp[i][j - 1] and dp[i - 1][j - 1], and the first row and column hold the base cases.

Fill the table so every cell's inputs are already computed, usually row by row, left to right. When a row only reads the row above it, keep two rows (or one, updated carefully) and memory drops from O(m · n) to O(n). Say whether you need the full table, for example to reconstruct the actual answer and not just its score.

A Python template

def paths_with_blocks(grid):
    """Ways from the top-left to the bottom-right moving only right or down;
    cells holding 1 are blocked."""
    rows, cols = len(grid), len(grid[0])
    row = [0] * cols                       # one row of the table, reused
    row[0] = 1 if grid[0][0] == 0 else 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                row[c] = 0                 # nothing passes through a block
            elif c > 0:
                row[c] += row[c - 1]       # from above (old value) + from the left
    return row[-1]

def longest_common_run(a, b):
    """Length of the longest contiguous run shared by strings a and b."""
    best = 0
    prev = [0] * (len(b) + 1)              # prev[j]: run ending at a[i-1], b[j-1]
    for i in range(1, len(a) + 1):
        cur = [0] * (len(b) + 1)
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1] + 1   # extend the run on the diagonal
                best = max(best, cur[j])
        prev = cur
    return best

Time and space

Time is the number of cells times the work per cell: O(m · n) for both examples. A full table is O(m · n) space; keeping one or two rows brings it to O(n), at the cost of not being able to walk back through the table to rebuild the answer itself.

Common mistakes

• Off-by-one between string indexes and table indexes; an extra row and column for empty prefixes avoids most of it.
• Overwriting a value in a single reused row before the next cell has read it.
• Forgetting the first row and column, which often have their own rule (one way along an edge until a block).
• Confusing a contiguous run with a subsequence, which have different recurrences.
• Keeping the full table when only the score is needed, or dropping it when the answer must be rebuilt.

How to explain it out loud

Define the cell out loud and draw a tiny table in words: "Cell i, j is the number of ways to reach row i, column j. Each cell gets the ways from above plus the ways from the left." Then say the fill order and why it works. Those sentences are the approach; the code is bookkeeping.

Trace a two-by-three example, mention blocked starting cells and empty strings, and give time and space, including the one-row saving. If Josh asks how you would return the actual edit sequence or path, say you would keep the full table and walk back from the last cell. Having that answer ready is code defense.