2D DP — choose the invariant

At a rolled grid cell, why does dp[c] mean “above” while dp[c-1] means “left”?

Label old and new values before updating.

1 / 11

Unique Paths — predict before coding

Classify paths by their final move into a cell. Right/down movement makes the grid acyclic, so path counts can be accumulated in row-major order.

Decision: A 2-by-4 grid permits right/down moves. Count its paths, then allow a diagonal down-right move. Derive the new second row and the additional rolled dependency.

Presenter notes

Model answer: Right/down alone gives 4 paths. With diagonals, first-row counts are [1,1,1,1] and second-row counts are [1,3,5,7]. Add above, left, and old diagonal because the three last-move classes are disjoint. Rolling needs a saved diagonal; using current-row left in its place invents routes. The supported UniquePaths API still allows only right/down moves.

Correctness argument: Let P(r,c) count paths from the top-left to (r,c). Except for the start, every path enters from above or from the left, and these final-move classes are disjoint. Therefore P(r,c)=P(r-1,c)+P(r,c-1), with out-of-grid predecessors contributing zero and the start contributing one. In an obstacle-free grid, each first-row or first-column cell has one path. During a left-to-right row update, dp[c] still stores the previous-row value from above and dp[c-1] already stores the current-row value from the left. Their sum is the required new count.

Debugging prompt: Test one row, one column, and symmetric dimensions. The contract requires the destination count to fit int; every prefix count is bounded by it because every prefix path can extend to the obstacle-free destination. A 100-by-100 grid exceeds 64-bit counting and is excluded by this numeric condition despite fitting the separate dimension bound.

2 / 11

Unique Paths II — predict before coding

An obstacle removes a vertex from the path graph. Its count must become zero immediately so it cannot leak an earlier row’s paths into the current row.

Decision: 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?

Presenter notes

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.

Correctness argument: The same disjoint last-move recurrence as Unique Paths applies to unblocked cells. A blocked cell has no valid paths ending there, regardless of its predecessor counts, so assign zero. Initialize only the start contribution, then scan left to right: old dp[c] counts arrival from above and new dp[c-1] counts arrival from the left. Resetting an obstacle preserves both the interpretation of the current cell and the next cell’s left predecessor. Induction over row-major order yields the endpoint count; a blocked start or finish consequently has zero paths.

Debugging prompt: Test blocked start/end, an obstacle in the first row, and a barrier cutting the grid in two. The grid is read-only. Exact counts require every intermediate count—not just the final possibly-zero endpoint—to fit int.

3 / 11

Minimum Path Sum — predict before coding

The set of predecessors is identical to path counting, but the aggregation changes: choose the cheaper predecessor, then pay for the current cell exactly once.

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

Presenter notes

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.

Correctness argument: Every path ending at (r,c) has a last predecessor above or to the left. Its cost equals that predecessor path cost plus grid[r][c]. Replacing the prefix by a cheaper path to the same predecessor preserves feasibility, so the optimum is the cell value plus the minimum optimal predecessor cost. Initialize the first row and first column by their unique paths. The rolled array keeps old-row costs above and already-updated current-row costs left, so each update implements the recurrence. The final entry is the minimum cost including both start and destination.

Debugging prompt: Test a single cell, one row, one column, and a locally cheap first move that is globally worse. Preserve the input grid and keep every intermediate sum representable.

4 / 11

Triangle — predict before coding

Choose a state with the direction of dependency made explicit: the minimum cost from a position down to the bottom. Then the already-computed row below summarizes every possible suffix.

Decision: 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?

Presenter notes

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.

Correctness argument: At the bottom, the minimum remaining cost at each position is its own value. For a position (r,c) above it, every valid next move goes to (r+1,c) or (r+1,c+1); choosing the cheaper optimal suffix and adding the current value is both feasible and no worse than any full path. This proves the recurrence by induction upward. Copying the last row keeps the input unchanged. Within a row, update left to right so dp[c] and dp[c+1] are still the two old lower-row values when used. Finally dp[0] summarizes every top-to-bottom path.

Debugging prompt: Test negative values and a single-row triangle. Each row must have one more element than the previous. Do not alias the last row as workspace when preserving the input is part of the reference behavior.

5 / 11

Worked trace — save the old diagonal

MinDistance("ab", "ac"): old row [1,0,1].

Save diagonal 1, then write boundary dp[0]=2.

Cell	Above	Left	Diagonal	Write	Next diagonal
b / a	0	2	1	1	0
b / c	1	1	0	1	1

Final row: [2,1,1]. One replacement suffices.

6 / 11

Faded trace — a match is a predecessor

MinDistance("ab", "ba"): old row [1,1,1].

Save diagonal 1; write dp[0]=2.

Column 1 matches b with b: write 1, carry old above 1.

Finish column 2 and the row. Is swapping adjacent bytes one allowed edit?

7 / 11

Edit Distance — predict before coding

A state compares two complete prefixes. Classify the last alignment step as a match, replacement, deletion, or insertion; each action removes at least one final byte from consideration.

Decision: 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?

Presenter notes

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.

Correctness argument: Let E(i,j) be the minimum unit-cost edits changing word1[:i] into word2[:j]. Transforming a nonempty prefix to empty requires i deletions; constructing a prefix from empty requires j insertions. Equal final bytes can align at no cost, leaving E(i-1,j-1). Otherwise the final edit is replacement, deletion, or insertion, whose predecessor costs are respectively diagonal, above, and left; minimizing them and adding one covers every optimal alignment and constructs a valid one. In the rolled row, save the old diagonal before overwriting each cell and carry it to the next column.

Debugging prompt: Test either empty input, identical strings, repeated bytes, and a substitution versus delete-plus-insert. This API indexes Go string bytes: one non-ASCII character may occupy multiple positions.

8 / 11

Interleaving String — predict before coding

A state records how many bytes have been consumed from each source. Their sum fixes the target position, so no third DP dimension is needed.

Decision: 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?

Presenter notes

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. A separate ambiguity appears with s1="ab", s2="ac", s3="acab": taking the first a from s1 fails, while taking a,c from s2 first succeeds. Preserve both reachable source-prefix states when bytes match either source.

Correctness argument: Let I(i,j) mean s1[:i] and s2[:j] can form s3[:i+j] while preserving each source order. The empty pair forms the empty target. A nonempty interleaving ends either with s1[i-1] from a reachable I(i-1,j), or with s2[j-1] from a reachable I(i,j-1), and the chosen byte must match s3[i+j-1]. These alternatives are exhaustive and either constructs a valid interleaving. Length mismatch is impossible before DP starts. Left-to-right row updates preserve old top and new left reachability, so the rolled recurrence computes the full table’s result.

Debugging prompt: Test length mismatch, one empty source, repeated shared prefixes, and equal character counts with the wrong order. Frequency equality is necessary but does not establish interleaving.

9 / 11

Maximal Square — predict before coding

A square ending at the current cell can grow only as far as all three neighboring squares support it: above, left, and diagonal. The weakest neighbor limits the side length.

Decision: 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?

Presenter notes

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.

Correctness argument: Let S(r,c) be the largest all-one square with bottom-right corner (r,c). A zero cell forces S=0. At a one cell, a square of side k+1 requires side-k support above, left, and diagonally above-left; otherwise one of its strips or interior corners contains a missing cell. Conversely, if all three neighbors support side k, their covered regions plus the current one cell cover the entire side-(k+1) square. Hence S=1+min(the three neighbors). Track the maximum side over every corner and square it only for the required area. Save the old diagonal while rolling rows.

Debugging prompt: Test a hollow square, all ones, a single row, and a zero that must reset old state. The input contains character bytes '0'/'1', not numeric bytes 0/1, and is not mutated.

10 / 11

Reconstruct and transfer

State each cell’s meaning, boundary values, predecessor guards, and update direction.

Return the requested count, cost, boolean, or area—not the internal state by accident.

11 / 11