Skip to content
Hari KharelStudy

Dynamic programming: 2D

intermediateCommon atGoogleAmazonMetaMicrosoftRead firstDynamic programming: 1DGrids and matricesPractise in the Sandbox →

2-D DP uses a state with two indices: dp[i][j] for “the first i characters of one string and the first j of another”, or “the cell at row i, column j”. Each cell reads a few neighbours (typically up, left and the diagonal), so a row-by-row fill works. O(m·n) time and space, and usually O(min(m, n)) space if you only need the number. To get the actual alignment or path, keep the table and walk back from the answer cell.

The idea in plain words

Section titled “The idea in plain words”

Comparing two strings feels like a 2-D problem because it is one. Any question about a and b can be asked about a prefix of each: “how similar are the first 3 letters of kitten and the first 4 of sitting?” Answer every such question, smallest first, and the big one at the bottom-right corner falls out.

Why up, left and diagonal? Look at the last characters of the two prefixes:

  • Diagonal (i−1, j−1): use both last characters (they match, or one replaces the other).
  • Up (i−1, j): drop the last character of a.
  • Left (i, j−1): drop the last character of b.

Grids work the same way with a different story: to reach a cell moving only right or down, you came from above or from the left.

The table also remembers how each cell got its value. Starting at the answer cell and repeatedly stepping to the neighbour that produced it gives you the alignment, the common subsequence, or the path, in O(m + n) extra time.

See it

Section titled “See it”

Pick a mode. Each arrow shows which neighbours a cell reads; the dim ones lost. After the fill, the green cells are the walk back from the answer. Try abcbdab vs bdcaba for LCS, or edit the grid costs.

Filling a 2-D table, then walking back
step through
a\bεsittingεkitten00000000000000
dp table
akitten
bsitting
cell being filledcell it came fromoption not takenreconstruction path
dp[i][j] = length of the LCS of the first i letters of "kitten" and the first j of "sitting". Row 0 and column 0 are empty prefixes: 0.
1 / 53

When to reach for it

Section titled “When to reach for it”
The problem says… Why 2-D DP fits
two strings or sequences: “similarity”, “fewest edits”, “common subsequence”, “interleave”, “match a pattern with * / ?” State = a prefix of each.
a grid: “number of paths”, “cheapest path” moving only right/down State = a cell; dependencies point backwards.
one sequence, but the answer is about a range [i..j] (palindromes, splitting, merging) State = the two ends. That’s interval DP.
“index into a list” and “remaining budget / capacity” State = (item, capacity). That’s knapsack.
a 1-D DP that needs to remember one more small thing Add a second dimension for it (k transactions, last colour used…).

How it works

Section titled “How it works”

The same five-step recipe as 1-D DP, with one extra decision about the table’s shape.

  1. State. dp[i][j] = the answer for the first i items of A and the first j of B (or for cell (i, j)). Use m + 1 by n + 1 so row 0 and column 0 mean “empty prefix”.
  2. Transition. Case on the last element(s): match / mismatch for strings, came-from-up / came-from-left for grids.
  3. Base cases. Row 0 and column 0. For edit distance, dp[i][0] = i (delete everything); for LCS, 0; for grid paths, the first row and column have one way in.
  4. Order. Each cell reads up, left, diagonal: fill row by row, left to right. (Interval DP is different: fill by length.)
  5. Answer and reconstruction. Usually dp[m][n]. Walk back to recover choices, or reduce to one or two rows if you only need the number.

Counting grid paths, already reduced to one row: row[c] still holds the value from the row above when you read it, and row[c−1] is the fresh value to the left.

count_paths.py
def count_paths(grid: list[str]) -> int:
    """Paths from top-left to bottom-right moving only right or down; '#' is blocked."""
    if not grid or grid[0][0] == "#":
        return 0
    cols = len(grid[0])
    # 1. state: row[c] = paths into cell (r, c) for the row being filled.
    #    Only the previous row is ever read, so one 1-D row is enough.
    row = [0] * cols
    row[0] = 1                                   # 3. base: one way to stand on the start
    for r in range(len(grid)):                   # 4. order: row by row, left to right
        for c in range(cols):
            if grid[r][c] == "#":
                row[c] = 0                       # blocked: nothing passes through
            elif c > 0:
                row[c] += row[c - 1]             # 2. from above (old row[c]) + from the left
    return row[-1]                               # 5. answer




if __name__ == "__main__":
    assert count_paths(["...", "...", "..."]) == 6     # C(4, 2)
    assert count_paths(["...", ".#.", "..."]) == 2
    assert count_paths([".#", "#."]) == 0
    assert count_paths(["."]) == 1
    print("ok")

Cheapest path with the full table kept, so the path itself can be recovered by walking back.

min_path.py
def min_path(cost: list[list[int]]) -> tuple[int, list[tuple[int, int]]]:
    """Cheapest top-left to bottom-right path moving right or down, and the path itself."""
    R, C = len(cost), len(cost[0])
    INF = float("inf")
    # 1. state: best[r][c] = cheapest total cost to reach (r, c), including its own cost
    best = [[INF] * C for _ in range(R)]
    best[0][0] = cost[0][0]                              # 3. base
    for r in range(R):                                   # 4. order: up and left are ready first
        for c in range(C):
            if r or c:
                up = best[r - 1][c] if r else INF
                left = best[r][c - 1] if c else INF
                best[r][c] = cost[r][c] + min(up, left)  # 2. transition
    # 5. answer, then walk back along whichever neighbour produced each value
    path = [(R - 1, C - 1)]
    r, c = R - 1, C - 1
    while (r, c) != (0, 0):
        if c == 0 or (r > 0 and best[r - 1][c] <= best[r][c - 1]):
            r -= 1
        else:
            c -= 1
        path.append((r, c))
    return int(best[R - 1][C - 1]), path[::-1]




if __name__ == "__main__":
    total, path = min_path([[1, 3, 1], [1, 5, 1], [4, 2, 1]])
    assert total == 7
    assert path == [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
    assert min_path([[5]]) == (5, [(0, 0)])
    print("ok")

What it costs

Section titled “What it costs”
Time Space
Brute force over all alignments / paths exponential (e.g. C(m+n, n) grid paths) O(m + n)
Full table O(m · n) O(m · n)
Two rows (or one row, updated in place) O(m · n) O(min(m, n)) if you index by the shorter string
Full table + walk back O(m · n) + O(m + n) O(m · n)
Hirschberg’s trick (reconstruct in linear space) O(m · n) O(m + n)

For two strings of length 1,000 that’s a million cells: fast. For 10⁵ each it’s 10¹⁰: too slow, and the interviewer wants a different idea (hashing, a special structure of the input, or a banded table if the answer is known to be small).

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Two strings: common subsequence, edit distance (with weighted or restricted operations), shortest common supersequence, interleaving, wildcard and regex-style matching.
  • One string, two ends: palindromic substructure, splitting into pieces. Fill by length, not row by row.
  • Grids: unique paths with obstacles, minimum path sum, largest square of 1s (dp = 1 + min(up, left, diag)), paths with two walkers (a 3-D state).
  • Index + budget: knapsack and its relatives.
  • Rolling to 1-D: whenever a row only reads the row above (and itself to the left), keep one row. Watch the update order: some recurrences need the old diagonal value, so save it in a variable before overwriting.

Pitfalls

Section titled “Pitfalls”
  • Off-by-one between string and table indices. dp[i][j] covers a[:i] and b[:j], so the last characters are a[i−1] and b[j−1].
  • Forgetting row 0 / column 0. Edit distance’s base cases are not zeros. Grids with an obstacle in the first row block everything to its right.
  • Overwriting the diagonal when compressing to one row. The value at row[j−1] from the previous row is gone once you’ve written the current row’s j−1. Keep it in a prev_diag variable.
  • Space-reducing too early. If you’ll need to reconstruct the path, keep the full table (or a parent table) until you’ve walked back.
  • Ties in reconstruction. Several walks back may be valid. If the problem asks for a specific one (lexicographically smallest, fewest operations of a kind), your tie-break during the walk has to match.
  • Recursion depth in top-down versions: 1,000 × 1,000 states can overflow the stack in Python. Bottom-up avoids it.

In the interview

Section titled “In the interview”
  • Say the state precisely: “dp[i][j] is the answer for the first i characters of a and the first j of b.”
  • Draw a small table (3×4) and fill three or four cells out loud. It shows the transition is right before you write code.
  • State the order and why: “each cell reads up, left and diagonal, so row by row works”.
  • Offer the space optimisation unprompted, and mention what you lose (reconstruction).
  • Expect: “now return the actual edits / path”, “strings are 10⁵ long” (needs a new idea), “only insertions and deletions allowed” (relates to LCS: m + n − 2·LCS), “weighted operations”.

Check yourself

Section titled “Check yourself”
Check yourself
pick one
In a common-subsequence table, a[i−1] ≠ b[j−1]. Why is dp[i][j] = max(dp[i−1][j], dp[i][j−1]) and not 1 + something?
Check yourself
pick one
You compress a 2-D table that reads up, left and diagonal into one row, updated left to right. Which value do you need to save before overwriting it?
Check yourself
pick one
Edit distance between a string of length m and the empty string is…

Practice on your own

Section titled “Practice on your own”

Classic exercises (not gym questions):

  • Unique paths in a grid with obstacles; then the minimum path sum.
  • Largest square of 1s in a binary matrix.
  • Is s3 an interleaving of s1 and s2?
  • Wildcard matching with ? (any one char) and * (any run).
  • Fewest deletions (from both strings) to make two strings equal.

Go deeper

Section titled “Go deeper”
  • Introduction to Algorithms (CLRS), §15.4 “Longest common subsequence” (§14.4 in the 4th edition), with the table and the walk back.
  • Kleinberg and Tardos, Algorithm Design, §6.6 “Sequence alignment” and §6.7 “Sequence alignment in linear space” (Hirschberg).
  • cp-algorithms: dynamic programming intro and its grid/knapsack follow-ups.
  • Jeff Erickson, Algorithms, ch. 3, the edit-distance derivation from a recursive definition.
Section titled “Related”
Dynamic programming: 1DThe 5-step recipe on a single sequence.
Advanced DP shapesIntervals, bitmasks and trees.
KnapsackA 2-D table over items and capacity.
Grids and matricesIndexing, neighbours and bounds in 2-D.