Week 14: 2-D Dynamic Programming

Pattern family: Dynamic Programming · Time budget: 15 hours · Prerequisites: Weeks 1 through 13 done, with the Week 13 five-step DP framework (state, transition, base case, order, answer) fresh, plus recursion and functools.lru_cache (Week 7) ready to use. · Cold-revisit obligation: Merge Intervals, Coin Change.

Overview

Last week the state fit on one index: dp[i] answered the subproblem ending at position i. This week the state needs two. That is the whole change. A grid has a row and a column. Two strings have a position in each. An interval has a left end and a right end. When one index cannot pin the subproblem down, you reach for dp[i][j], a table instead of a row, and the same five-step recipe from Week 13 still runs: define the state, write the transition, set the base cases, choose the fill order, extract the answer.

The recipe does not get harder; the bookkeeping gets wider. The transition now reads from neighboring cells in two directions (usually the cell above, the cell to the left, and the diagonal), the base cases are now a whole first row and a whole first column instead of a single dp[0], and the complexity is the table size (rows times columns) times the per-cell work. Most of this week is the same recognition move as last week, with one extra beat: when you catch yourself needing to track two positions at once, do not force it into a 1-D array; name the two-index state and build the table.

flowchart TD
    Q["Read the problem"] --> A{"Is this DP? Overlapping<br/>subproblems, answer for one<br/>state built from smaller states?"}
    A -->|no| G["Probably greedy, a single pass,<br/>or a different pattern.<br/>Keep reading the cues."]
    A -->|yes| B{"Can one index name<br/>the state: dp[i]?"}
    B -->|"yes, one index is enough"| H["1-D DP (Week 13):<br/>dp[i], a single row."]
    B -->|"no, I need two positions<br/>at once"| W["2-D DP: define dp[i][j],<br/>the transition, the base row<br/>and column, the fill order,<br/>the answer cell."]

Notice: the fork is one index versus two. A single position (a prefix, a step, an amount) stays 1-D; two positions at once (a row and a column, a spot in each of two strings, the two ends of an interval) is the tell for 2-D. Naming which one the problem needs, out loud, before any code (principle 1) is the move this whole week trains.

Warm-Up: Retrieve Before You Begin

Answer from memory, no peeking. This pulls forward the two tools 2-D DP leans on hardest: last week’s framework and the one Python idiom that breaks a 2-D table if you get it wrong.

From Week 13: state the five steps of the DP framework, in order, in your own words.
From the refresher (the pitfalls section): why is grid = [[0] * cols] * rows a bug, and what is the correct way to build a rows by cols table of zeros?
From Week 13: when does a 1-D DP collapse to two rolling variables instead of a full array, and what makes that possible?

Check your recall

1. **State** (one sentence: "`dp[i]` is ..."), **transition** (how `dp[i]` builds from smaller cells, the recurrence), **base case** (the smallest subproblem you answer directly), **order of computation** (fill cells so every cell a transition reads is already final), **answer extraction** (which cell or aggregate is the result). This week the state takes two indices, `dp[i][j]`, but the five steps are unchanged. 2. `[[0] * cols] * rows` builds one inner list and then stores `rows` references to that *same* list, so writing `grid[0][0] = 1` changes every row at once. The correct form builds each row independently: `grid = [[0] * cols for _ in range(rows)]`. This is the signature bug of this week; see the misconception callout below. 3. A 1-D DP collapses to a constant number of rolling variables when the transition only reads the last one or two cells (Climbing Stairs, House Robber: `dp[i]` reads `dp[i-1]` and `dp[i-2]`). When a cell can read much further back, you keep the whole array. The 2-D analogue is keeping two rows instead of the full table, which works whenever a row only depends on the row above it.

Learning objectives

By the end of this week you can:

Recognize the two-index cue (a grid, two strings, two endpoints, an interval on a sequence) and reach for a dp[i][j] table without being told.
Define the two-index state precisely: write the one sentence “dp[i][j] is …” that every correct 2-D DP solution starts from.
Construct the match/mismatch transition for string DP, naming which neighboring cells (above, left, diagonal) each case reads.
Initialize a 2-D table correctly with [[0] * cols for _ in range(rows)], and explain why the aliasing form is wrong.
Analyze the time and space complexity from the table dimensions times the per-cell work, and say when the table reduces to one or two rows.
Distinguish grid DP, string DP, and interval DP, and explain why Burst Balloons is solved by asking “what was burst last.”
Defend every line of each solution you commit, from memory, with no AI open, including why the fill order is correct.

Recognition cue

“Overlapping subproblems, and the state needs two positions at once” almost always means 2-D dynamic programming. The surface tells: a grid you move across (Unique Paths), two sequences compared position by position (Longest Common Subsequence, Edit Distance, Regular Expression Matching), or a span on a sequence described by its two endpoints (Burst Balloons). The deeper test is the same as last week: a brute-force recursion would recompute the same (i, j) pair many times. The new beat is that one index is not enough to name the subproblem; the moment you find yourself wanting to say “the answer for the first i of this and the first j of that,” you are in 2-D.

Core concepts to internalize this week

The two-index state is the whole game. Before anything else, write one sentence: “dp[i][j] is the [answer] for [the subproblem fixed by the pair (i, j)].” For Edit Distance it is “the edit distance between the first i characters of word1 and the first j characters of word2.” For Longest Common Subsequence it is “the length of the LCS of the first i of text1 and the first j of text2.” If you cannot write that sentence, no code will save you.
Match versus mismatch in string DP. When you compare two strings, the cell dp[i][j] splits on whether the current characters match. If they match, you usually carry the diagonal dp[i-1][j-1] (the two characters pair off and you keep the answer for the shorter prefixes). If they do not match, you combine neighbors: for Edit Distance, 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (delete, insert, replace); for LCS, max(dp[i-1][j], dp[i][j-1]) (drop one character from one side or the other). Naming which neighbors each case reads is the bulk of the work.
Base cases are a row and a column. In 1-D you set dp[0]. In 2-D you set an entire first row and first column, because either string can be empty. For Edit Distance, turning the empty string into a string of length k costs k insertions, so dp[0][j] = j and dp[i][0] = i. Getting that border right is half of getting the table right.
Fill order in two dimensions. The transition for dp[i][j] reads cells with smaller indices (above, left, or up-left). So sweep the table so those are already filled: typically row by row, left to right, after seeding the borders. State the order out loud and check that every cell a transition reads is final before you read it.
Interval DP and the “what was burst last” reframing. Some 2-D problems index a span by its two endpoints rather than two separate sequences. Burst Balloons is the example: dp[i][j] is the most coins obtainable from the open interval between balloons i and j. The trick that makes it work is to ask not which balloon you burst first (that splits the array into two pieces whose neighbors keep changing) but which balloon k you burst last in the interval. If k is last, then when it pops its neighbors are exactly the fixed endpoints i and j, and the two sub-intervals (i, k) and (k, j) are already solved and independent. That reframing is the entire lesson of interval DP.
Two cases for * in regex DP. Regular Expression Matching is string DP with a twist: the pattern character * can mean “zero of the preceding element” or “one more of the preceding element.” So the transition for a * is a disjunction: either skip the x* pair entirely (match zero), or, if the current text character matches the element before the *, consume that text character and stay on the same * (match one more). Holding both branches of that “or” in your head is what makes regex DP click. The . is the easy part: it matches any single character.
Space optimization to one or two rows. When dp[i][j] only reads the current row and the row directly above, you do not need the full table; two rows (or, with care, one row updated in place) suffice. That drops space from O(m·n) to O(min(m, n)) if you orient the shorter dimension as the row. Edit Distance, LCS, and Unique Paths all admit this. The time stays the same; only the memory shrinks.

Common misconception. “I can build a 2-D table the same way I build a 1-D one: dp = [[0] * cols] * rows.” Reality. That is the signature bug of this week. [[0] * cols] * rows creates one inner list and then makes rows references to that same list, so the rows are aliases of each other. Writing dp[1][2] = 5 changes column 2 in every row at once, and your table silently fills with garbage. Always build each row independently:
dp = [[0] * cols for _ in range(rows)]
The list comprehension runs [0] * cols afresh on each iteration, so you get rows distinct lists. If a 2-D DP gives bizarre results that no logic error explains, check this line first. It is the most common way a correct recurrence produces a wrong answer this week.

Heavy concept ahead. Defining dp[i][j] is roughly 80 percent of the work. Everything else (the transition, the borders, the fill order, the answer cell) follows almost mechanically once the state is named precisely, and is nearly impossible to get right when the state is vague. The discipline: before you write a single line, finish this sentence out loud and in writing, with no hand-waving about what i and j range over and whether they count characters or index into the array:

“dp[i][j] is the __ for the first i __ and the first j ___.” If the two halves of “first i” and “first j” are not crisp, stop and fix the definition; do not start coding. The match/mismatch transition, the base row and column, and the answer cell are all read directly off a correct state sentence. A wrong or fuzzy state is the single largest source of broken 2-D DP, and no amount of debugging the loop body will fix a state that was never well defined. The Pattern Card asks you to write this sentence; the canonical deep-dive walks it; the debrief checks it.

Python idioms this week

You are not yet expected to be fluent, so here is the toolbox this week uses. If any is unfamiliar, open the Python refresher before Monday.

2-D table initialization, done correctly: dp = [[0] * cols for _ in range(rows)]. Never [[0] * cols] * rows; that aliases one row across all rows (see the misconception callout). This is the one idiom that, gotten wrong, silently breaks the whole week.
Indexing into the table with two subscripts: dp[i][j], reading neighbors as dp[i-1][j] (above), dp[i][j-1] (left), dp[i-1][j-1] (diagonal).
Iterating two sequences by index with nested loops: for i in range(1, m + 1): for j in range(1, n + 1):, where i and j are 1-based so that dp[0][...] and dp[...][0] hold the empty-string base cases.
A character compare that drives the branch: if word1[i-1] == word2[j-1]: (note the -1: when the table is 1-based, the character for cell i lives at string index i-1).
min(...) over the three edit operations, max(...) over the two LCS drops, seeded from neighboring cells.
functools.lru_cache(maxsize=None) for the top-down form, where the two arguments (i, j) are the state; both must be hashable (ints are).
String slicing s[j:] or s[i:] to reason about suffixes when you think top-down (it copies, so the slice itself costs O(length); prefer passing indices when you can).

These are tools you are allowed to know cold in an interview. The pattern (the two-index state, the transition, why the fill order is correct) is the part you build yourself.

Pattern Card requirement

Before you solve the canonical problem, write your Pattern Card at .tutor/pattern-cards/2d-dynamic-programming.md. It must contain:

The recognition cue, in your own words (lead with the one-index-versus-two test).
The algorithmic skeleton in pseudocode (the five-step framework with a two-index table: seed the border row and column, then sweep i then j).
Time and space complexity, general form (table dimensions times per-cell work; plus the space win from keeping two rows).
Three edge cases (an empty string on one side, a single-row or single-column grid, and a one-element interval are good starts).
One war story (a bug you actually hit this week; the [[0]*c]*r aliasing trap is a strong candidate); fill this in at the end of the week.

The first four sections must be present before you start the canonical deep-dive. The tutor will probe the card; it will not write any of it for you.

Canonical deep-dive

Problem: Edit Distance (https://leetcode.com/problems/edit-distance/)

Edit Distance is this course’s home for 2-D string DP: the match/mismatch transition, the base row and column, and the exact O(m·n) complexity, all on a problem where the two-index state is unavoidable. The full guided walk-through, with the state definition, the recurrence as a relation, the base cases, the fill order, and the two-row space optimization, is in canonical/edit-distance.md. Work it there. You will implement it yourself, in your own work repo, and write a short debrief. The walk-through is deliberately not an answer key: it shows you how to think, and stops short of code you could paste.

Practice set

Four problems, in this order. Each has its own folder under practice/ with the problem link, a complexity target for you to fill in, and the debrief template. Do not skip ahead.

Unique Paths (practice/unique-paths/). The gentlest 2-D DP: count the paths through a grid moving only right or down. The state is “ways to reach cell (i, j),” and the table is the grid itself.
Longest Common Subsequence (practice/longest-common-subsequence/). The string-DP workhorse, and the direct sibling of Edit Distance: same table shape, a simpler match/mismatch transition.
Burst Balloons (practice/burst-balloons/). Interval DP. The reframing that unlocks it is asking which balloon was burst last in a span, not first; that is the whole problem.
Regular Expression Matching (practice/regular-expression-matching/). String DP with the dual case of * (zero copies, or one more). The hardest problem of the week; expect to lean on the framework hard.

Each problem follows the five-beat rhythm.

The five-beat rhythm (every problem)

Pattern Card is written (you did this Monday).
Name the pattern aloud and write your approach as a plain-English comment before any code.
Struggle floor: 25 minutes unaided.
Hint ladder if needed: six rungs, one per ask.
Debrief: the five questions, in your commit message, before the next problem.

Reflect

Ten minutes in your notebook, in writing:

Explain it back: describe to a peer who just finished Week 13 how a 1-D DP becomes a 2-D DP, in five sentences. What changes about the state, the base case, and the fill order, and what stays the same?
Connect: Longest Common Subsequence and Edit Distance share a table shape and a match/mismatch split. Write the one sentence of state for each, and name the one place their transitions differ.
Monitor: which beat is still the one you fumble in two dimensions: naming the two-index state, getting the base row and column right, or trusting the fill order? Write the one sentence that would steady it.

Knowledge Check

Answer from memory first. Items marked ⟲ are spaced callbacks to earlier material.

What is the one-sentence test that tells you a problem is 2-D DP rather than 1-D DP?
For Edit Distance, what is the state dp[i][j], what does the match case do, and what does the mismatch case do?
In Burst Balloons, why is the state defined over “which balloon was burst last in the interval” instead of first? What goes wrong with “first”?
⟲ From the refresher: why does dp = [[0] * cols] * rows corrupt your table, and what is the correct initialization?
⟲ From Week 13: top-down memoization and bottom-up tabulation for the same 2-D recurrence have the same time complexity. Name one concrete reason you might prefer bottom-up here.

Answer key

1. Whether one index can name the subproblem. If a single position (a prefix, a step, an amount) pins it down, it is 1-D; if you need two positions at once (a row and a column, a spot in each of two strings, the two ends of an interval), it is 2-D and you build `dp[i][j]`. 2. `dp[i][j]` is the edit distance between the first `i` characters of word1 and the first `j` characters of word2. If the current characters match (`word1[i-1] == word2[j-1]`), carry the diagonal: `dp[i][j] = dp[i-1][j-1]` (no operation needed for this pair). If they do not match, take `1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])`, the one operation being a delete, an insert, or a replace respectively. 3. If you ask which balloon you burst *first*, popping it splits the array into two pieces, but the neighbors of every remaining balloon shift as balloons disappear, so the two pieces are not independent and you cannot reuse their answers. Asking which balloon `k` is burst *last* in the open interval `(i, j)` fixes its neighbors at exactly `i` and `j` (everything else in the interval is already gone), so the coins from popping `k` are `vals[i] * vals[k] * vals[j]`, and the sub-intervals `(i, k)` and `(k, j)` are independent and already solved. Independence is what makes the recurrence valid. 4. `[[0] * cols] * rows` builds one inner list and stores `rows` references to that same list, so the rows are aliases; writing one cell changes that column in every row. Build each row independently with `[[0] * cols for _ in range(rows)]`, which runs `[0] * cols` afresh each iteration. 5. Any one of: bottom-up avoids Python's recursion-depth limit, which a top-down solve on long strings can hit; bottom-up makes the two-row space optimization (O(min(m, n))) obvious; bottom-up has no per-call function overhead. The complexity is identical; the engineering differs.

Cold revisit

This Friday, before any new work, re-solve two prior problems cold: no notes, no prior code open, no AI, the standard 25-minute floor on each. The full instructions are in revisit.md.

Merge Intervals (Week 10, Tries and Intervals). https://leetcode.com/problems/merge-intervals/
Coin Change (Week 13, 1-D Dynamic Programming). https://leetcode.com/problems/coin-change/

One is the Intervals pattern from four weeks back, which no Friday has pulled back since you met it (cross-course recognition); the other is last week’s canonical DP problem at a deliberately short interval (does the framework still fire when it is no longer the current week’s pattern?). Debrief each at the end and log the outcome in .tutor/revisit-log.md.

How to know you are done with this week

Pattern Card complete at .tutor/pattern-cards/2d-dynamic-programming.md, including the war-story field.
Canonical deep-dive done: Edit Distance implemented yourself (bottom-up, and ideally the top-down memoized version too), with your short debrief (in your work repo).
Four practice problems solved, each with a five-question debrief in its commit message.
.tutor/revisit-log.md updated by the tutor with this week’s problems and the two cold revisits, with dates.
.tutor/progress.md updated to “Week 14 complete; ready for Week 15.”

If any of the above is missing, the week is not done. The tutor will not advance you to Week 15 until all five are present.

Resources

Free, no account required:

[Article] Dynamic programming, the idea: https://en.wikipedia.org/wiki/Dynamic_programming
[Article] Edit distance (Levenshtein): https://en.wikipedia.org/wiki/Edit_distance
[Article] Longest common subsequence: https://en.wikipedia.org/wiki/Longest_common_subsequence
[Docs] Python functools.lru_cache: https://docs.python.org/3/library/functools.html#functools.lru_cache