2D DP: preserve the meaning of every neighbor

Reader guide and study workflow · Complete course map

Two dimensions are needed when a subproblem depends on a pair of positions: a grid cell, two string prefixes, or a triangle row and column. The important question is not the table’s shape but which predecessors can lead to the current state.

Grid paths: same graph, different aggregation

For right/down paths, a path enters a cell from above or from the left. Counting adds the two disjoint predecessor classes; minimizing cost takes the cheaper predecessor then adds the current cell value. Obstacles force the count at their cell to zero.

A boundary-safe counting recurrence is:

for r = 0..m-1:
    for c = 0..n-1:
        if cell is blocked: P[r][c] = 0
        else if r == 0 and c == 0: P[r][c] = 1
        else:
            top = P[r-1][c] if r > 0 else 0
            left = P[r][c-1] if c > 0 else 0
            P[r][c] = top + left

Do not initialize every boundary cell to one when obstacles exist: a blocked cell can make all later boundary positions unreachable. For minimum path cost, initialize the start with its value and first-row/column cells by their unique predecessor; there is no zero-cost imaginary path entering from outside the grid.

Triangle: reverse the dependency direction

Define T(r,c) as the minimum remaining path total from that position to the bottom. Then T(r,c)=triangle[r][c]+min(T(r+1,c),T(r+1,c+1)). The bottom row is already a set of complete answers. Work upward, copying rather than aliasing the bottom row when the input must remain unchanged.

Edit distance: compare two prefixes

E(i,j) is the minimum edit cost between the first i and j bytes. The empty-prefix boundaries are E(i,0)=i and E(0,j)=j. If the last bytes match, align them for free and use the diagonal. Otherwise replacement uses the diagonal, deletion uses above, and insertion uses left; choose the smallest predecessor and add one.

These are byte positions in the preserved Go API. A Unicode character can span several bytes. A rune-based distance would be a different observable definition, not a transparent optimization.

Interleaving: the third index is determined

I(i,j) means the first i bytes of s1 and first j bytes of s2 form the first i+j bytes of s3 in source order. After rejecting a length mismatch, begin at I(0,0)=true. For every other cell, allow an above predecessor only when i>0 and its next s1 byte matches; allow a left predecessor only when j>0 and its next s2 byte matches. OR the guarded alternatives. Duplicate matching bytes can require keeping both alternatives reachable.

Maximal square: a side length, not a nearby-one count

At a zero cell the largest ending square has side zero. At a one cell, its side is one plus the minimum side supported above, left, and diagonally above-left. Each neighbor certifies a different part of the proposed larger square. Taking a maximum would allow the strongest neighbor to hide a missing strip or corner. Track the largest side across all endpoints, then return its square as the area.

Prerequisites and readiness

Know 1D prefix DP, row/column indexing, and the difference between a counting sum, minimum cost, boolean reachability, and geometric extent. Derive a full table before compressing it.

Start with Unique Paths and its obstacle variant, then change addition into minimization for Minimum Path Sum. Triangle changes the dependency direction. For Edit Distance, finish the saved-diagonal trace below before implementing a rolled row. Interleaving and Maximal Square test whether you can derive a new state meaning rather than copy a numeric recurrence.

Reasoning workshop: old row, new row, and saved diagonal

Label memory by time as well as position

During a left-to-right grid update, dp[c] means the old row’s answer above the current cell. dp[c-1] already means the new row’s answer to its left. Their sum or minimum is valid precisely because these are different time slices. Write “old” and “new” above the entries when hand-tracing.

For the obstacle grid [[0,0,0],[0,1,0],[0,0,0]], successive rolled arrays are [1,1,1], [1,0,1], [1,1,2]. Failing to reset the center would let paths travel through a blocked vertex. A one-row grid with a blocked middle cell is the smallest counterexample to initializing all boundary counts to one.

Direction changes when dependency changes

Triangle updates read the two children in the old lower row. Given lower costs [6,5,7] and current values [3,4], left-to-right computes [8,9]. Right-to-left first writes 9 into the location still needed as the old child cost 5, producing an incorrect 9 for the first position. “Always roll left-to-right” is not a universal rule; derive the direction from which old values remain needed.

The diagonal needs its own saved value

Edit Distance and Maximal Square need old dp[c-1], which the left-to-right loop has already overwritten. Save old dp[c] before the write; after computing the cell, carry that saved value as the next diagonal. At the start of each row, initialize the diagonal to the correct boundary state. The max-square diagonal starts at zero; edit distance begins from the old empty-target cost.

Work MinDistance("ab", "ac"). Rows consume source bytes and columns consume target bytes, so the complete prefix table is:

Source prefix / target prefix	empty	a	ac
empty	0	1	2
a	1	0	1
ab	2	1	1

Before the final row, rolled memory is [1,0,1]. Save the old empty-target value 1 as the diagonal, then set dp[0]=2. Each update must distinguish three different predecessor times:

Cell	Old above	New left	Saved old diagonal	Write	Next diagonal
E(2,1), b versus a	0	2	1	1 + min(0,2,1) = 1	0
E(2,2), b versus c	1	1	0	1 + min(1,1,0) = 1	1

The old dp[1]=0 must survive as the second cell’s diagonal even after dp[1] becomes 1. Carrying the newly written value instead would calculate the last cell as 2 and miss the single replacement b → c. Save above before the write; assign that saved value to the diagonal after the write. This is why two adjacent array positions alone cannot supply all three dependencies.

Faded practice: finish a different row

For MinDistance("ab", "ba"), the row after consuming source a is [1,1,1]. Start the next row with diagonal 1 and dp[0]=2.

1. For column 1, b matches b, so write the saved diagonal 1 and carry old above 1.
2. Complete column 2, where b and a differ. Give (above,left,diagonal), the new row, and the final edit distance.
3. Does treating an adjacent transposition as one edit agree with this API?

Model answer: neighbors refer to prefixes

At column 2, (above,left,diagonal)=(1,1,1), so write 2. The completed row is [2,1,2] and the distance is 2. Two replacements, or one deletion plus one insertion, attain it. Adjacent transposition is not a primitive operation in this exercise; accepting it for cost 1 would change the contract.

Boolean alternatives cannot be greedily merged

Interleave "ab" and "ac" into "acab". Both sources begin with a, but consuming it from the first source leaves next candidates b and a, neither matching c. Consuming a,c from the second source first succeeds. A boolean DP preserves both reachable source-prefix pairs without needing to enumerate entire histories.

Certificates and independent checks

For an obstacle-free 3-by-3 grid, choosing two down positions among four moves gives 6 paths, an independent check against table accumulation. For maximal square, enumerate every candidate top-left and side length on a tiny board, testing all contained cells; that is slower than the recurrence but makes a useful oracle. For edit distance, a full matrix provides an implementation independent of the rolled memory update and catches diagonal-overwrite errors.

Counts and costs must still fit the preserved int API; dimensions alone do not guarantee that. Unique Paths explicitly guarantees a representable destination count. With no obstacles, every prefix path can be extended to the destination, so this also bounds each intermediate count. Unique Paths II instead requires every cell’s path count to fit: an obstacle can make the destination unreachable after many paths have already accumulated elsewhere.

Minimum Path Sum requires each cell’s minimum prefix sum to fit, and Triangle requires each position’s minimum suffix sum to fit. These conditions protect the states actually used by their recurrences. A small final answer alone would not establish intermediate representability, especially when negative triangle values can later reduce a large suffix cost.

Reconstruction lab and answer key

Unique Paths

A 2-by-4 grid allows only right and down moves. How many paths exist? Now add a diagonal down-right move. Derive the new predecessor set, complete both path-count rows, and explain what extra information a rolled implementation would need.

Model answer

Without diagonals, choose which of four moves is the single down move: 4 paths. With diagonals, the first row is [1,1,1,1] and the second is [1,3,5,7]. Each non-start cell adds paths from above, left, and above-left where those predecessors exist; last-move classes are disjoint. At (1,1), 1+1+1=3; the remaining entries are 1+3+1=5 and 1+5+1=7. Rolling now needs the old diagonal as well as old above and new left. Save it before overwrite, as in the later edit-distance lesson. The graded UniquePaths API retains right/down movement only.

Unique Paths II

For obstacle rows 0100 / 0000 / 0010, the first rolled row is [1,0,0,0]. Complete the next two rows. A buggy obstacle branch says continue without writing zero; where does its first incorrect count appear?

Model answer

The remaining rows are [1,1,1,1] and [1,2,0,1], so there is one path to the destination. On the third row the obstacle at column 2 must replace old count 1 with zero. Merely continuing preserves that 1 and lets the destination incorrectly receive 1+1=2. The first blocked row alone would not reveal this bug if the workspace began with zeros beyond the start.

Minimum Path Sum

For [[1,3,1],[1,5,1],[4,2,1]], what is the minimum path sum and which path achieves it?

Model answer

The minimum is 7 along values 1,3,1,1,1: move right, right, down, down. The start and destination are each included once.

Triangle

For triangle [[2],[3,4],[6,5,7],[4,1,8,3]], the first bottom-up update gives [7,6,10]. Finish the remaining two updates. A learner aliases the final input row as workspace: does a correct numeric answer establish that the input was preserved?

Model answer

The next costs are [9,10], then [11]. A path attaining 11 is 2,3,5,1. The numeric answer does not establish ownership: assigning the bottom-row slice directly aliases its backing array, so rolling writes alter the caller’s triangle. Copy that row before using it as scratch space and compare the input before and after the call when checking preservation.

Edit Distance

For MinDistance("aa", "a"), row 1 is [1,0]. Complete row 2 and explain why a matching final byte does not make the distance zero. What boundary value must be saved before dp[0] is changed?

Model answer

Save old dp[0]=1 as the diagonal, then set dp[0]=2. The matching final bytes use that old diagonal, so the row becomes [2,1] and the answer is 1: one source a still needs deletion. Saving the new boundary 2 instead would also be wrong. A match contributes zero additional cost; it does not erase the cost of the remaining prefixes.

Interleaving String

For s1="ab", s2="cd", compare targets "acbd" and "adbc". They have identical byte counts. Which is an interleaving, and at which target prefix does the other become impossible?

Model answer

acbd is valid by taking a from s1, c from s2, b from s1, then d from s2. adbc fails at prefix ad: after taking a, the available next bytes are b and c, not d. Source order is part of the state; global frequency equality cannot prove reachability. The worked shared-prefix example above addresses the separate mistake of keeping only one reachable state.

Maximal Square

For byte rows 01 / 11, fill the square-side table. At the final cell, above and left both support side 1, but the old diagonal is zero. What goes wrong if the recurrence ignores the diagonal?

Model answer

The side rows are [0,1] and [1,1]; the maximum side is 1 and the returned area is 1. At the final cell, ignoring diagonal zero would invent side 2 and area 4 over a square containing the top-left zero. The minimum must include all three neighbors, and the returned answer squares the maximum side exactly once.

Problems in this module

• Unique Paths
• Unique Paths II
• Minimum Path Sum
• Triangle
• Edit Distance
• Interleaving String
• Maximal Square

Interactive checkpoint

Open the 2D DP quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

2D DP

Pattern A: Grid DP (count or min)

Pattern B: Triangle bottom-up

Pattern C: Edit distance / alignment

Pattern D: Interleaving DP (two prefixes -> one)

Pattern E: Largest square of 1s

When to use 2D DP (checklist)

Common failures (checklist)

Why these problems fit

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable