Classic 2D DPs: A Grid of Subproblems

"When a problem juggles two things at once — two strings, or items-plus-a-budget — the state needs two numbers, and the DP table becomes a grid. These 2D DPs are the workhorses behind spell-check, DNA alignment, and file diffs."

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

These aren't academic toys. Edit distance powers spell-checkers ('did you mean…?' ranks candidates by edit distance) and fuzzy matching. Longest common subsequence is the engine of diff and version control (finding what changed between two files) and of DNA/protein sequence alignment in bioinformatics. 0/1 knapsack (max value within a weight limit, each item taken or not) models budgeting, resource allocation, and cargo loading. The 2D table that looks like an exercise is, in production, how your editor diffs files and how geneticists compare genomes.

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