Classic 2D DPs: A Grid of Subproblems

"When a problem juggles two axes—two strings, or items plus a budget—the state becomes a grid. Edit distance and LCS are foundational workers under spell suggestions, diffs, and DNA alignment. The whole product is rarely this one table, but plenty of it stands on the table."

Two Dimensions of State

A 2D DP has a subproblem identified by a pair of numbers, so the table is a grid. The most common shape: two sequences, where dp[i][j] answers a question about 'the first i of sequence A and the first j of sequence B.' Another: dp[i][w] = 'using the first i items within budget w.' Each cell is computed from its neighbors — usually the cell above, the cell to the left, and/or the diagonal — and you fill the grid in an order (typically row by row) that guarantees those neighbors are ready before you need them.

Edit Distance: the Canonical 2D DP

The edit distance (Levenshtein distance) between two strings is the minimum number of single-character insertions, deletions, or substitutions to turn one into the other. Define dp[i][j] = the edit distance between the first i characters of A and the first j of B. The recurrence reads like a decision: if the current characters match, dp[i][j] = dp[i-1][j-1] (no edit needed); otherwise it's 1 + min of three choices — delete (dp[i-1][j]), insert (dp[i][j-1]), or substitute (dp[i-1][j-1]). Three neighbors, one min. The base cases (turning a string into the empty string costs its length) seed the first row and column.

A 2D DP indexes its state by a pair (i, j) — usually positions in two sequences, or (index, capacity). Each cell depends on a few neighbors (up / left / diagonal); fill the grid in dependency order. Edit distance and LCS are the canonical examples, powering diff, spell-check, and DNA alignment.

Where 2D DPs Run the World

Edit distance and LCS are important foundations for fuzzy matching, diffing, and biological sequence comparison. Production tools may instead or additionally use Myers diff, tokenization, heuristics, and domain-specific scoring. Likewise, knapsack is a useful model for some allocation problems, not the universal engine behind them.

Pippa's Confession

The edit-distance grid felt arbitrary until Dad had me label what one cell meant: dp[3][2] is 'the cost to turn the first 3 letters of A into the first 2 letters of B.' Once each cell had a sentence, the three-way min stopped being a formula and became three obvious choices — delete, insert, or substitute. The trick that unlocked every 2D DP for me was refusing to write a recurrence until I could say, in plain words, exactly what dp[i][j] represents.

Code

Edit distance: the canonical 2D DP·python

# EDIT DISTANCE (Levenshtein): min insertions/deletions/substitutions.
# dp[i][j] = edit distance between A[:i] and B[:j].
def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i              # base: turn A[:i] into '' -> i deletions
    for j in range(n + 1):
        dp[0][j] = j              # base: turn '' into B[:j] -> j insertions
    for i in range(1, m + 1):
        for j in range(1, n + 1):       # fill row by row (dependencies ready)
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]        # match: no edit
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # delete from A
                    dp[i][j-1],    # insert into A
                    dp[i-1][j-1],  # substitute
                )
    return dp[m][n]

print(edit_distance("kitten", "sitting"))   # 3  (k->s, e->i, +g)
# Each cell = 'cost to transform this prefix of A into this prefix of B'.
# This exact DP powers spell-check ranking and is kin to diff/DNA alignment.

Exercise

Build the first two rows of the edit-distance table for A='ab' and B='ac'. Fill in dp[0][*] and dp[1][*] using the rules (match → diagonal; mismatch → 1 + min of the three neighbors). State in words what dp[1][1] represents and why it equals what it does. Then name two real systems that run on edit distance or its cousin LCS.

Hint

dp[0] = [0,1,2] (turn '' into prefixes of 'ac'). dp[1][0]=1; dp[1][1]: A[0]='a'==B[0]='a' → diagonal dp[0][0]=0. dp[1][1]=0 means 'a'→'a' costs nothing. Real systems: spell-checkers (rank suggestions by edit distance) and diff/version control + DNA alignment (longest common subsequence).

Two Dimensions of State

Edit Distance: the Canonical 2D DP

Where 2D DPs Run the World

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0