2-D Dynamic Programming

11 questions, and the hardest DP in the set. The second dimension means different things in different problems, and recognising which kind you have is most of the work.

What the second dimension actually is

Meaning	Questions
a second sequence index	2, 6, 8, 9, 11
a grid coordinate	1, 7
a state in a machine	3
a capacity / target	4, 5
an interval endpoint	10

Best Time to Buy and Sell with Cooldown is "2-D" only in that its second index is a state label — HOLD, SOLD, REST. Burst Balloons is 2-D because dp[i][j] is an interval.

The dependency pattern decides the fill order

Two indices, and the cells each one reads

Most recurrences read at most three neighbours — above, left, diagonal — so row-major, left-to-right works. Interval DPs are the exception: they read a whole range and must be filled by increasing interval length.

Rolling: which direction, and why

The loop direction follows from which generation you need to read, not from convention.

Need	Direction	Questions
current row's left neighbour	ascending	1 (Unique Paths)
previous row's diagonal	descending	8 (Distinct Subsequences), 0/1 knapsack
both above and diagonal	two rows, or one plus a saved variable	2 (LCS), 9 (Edit Distance)
a whole range	cannot roll	10 (Burst Balloons)

Unique Paths rolls to one array with dp[j] += dp[j-1], where dp[j] is still the stale "above" and dp[j-1] is the fresh "left". Edit Distance rolls to one array plus one variable holding the diagonal — the leaner alternative to LCS's two rows.

Loop order can change the answer

Coin Change II has two independent loop-order decisions, and conflating them is the usual confusion:

Decision	Choice	Effect
which loop is outer	coins	combinations, not permutations
which direction the amount runs	ascending	unlimited reuse, not 0/1

Verified: for amount = 5, coins = [1,2,5], coins-outer gives 4 and amount-outer gives 9. Same array, same recurrence, same complexity.

The reframe that makes Burst Balloons tractable

Asking "which balloon bursts first" leaves subproblems that interact — the halves become adjacent. Asking "which bursts last" fixes its neighbours as the interval's boundaries, making the halves genuinely independent.

O(n!) → O(n³), purely from changing the question. The same shape solves Matrix Chain Multiplication and Optimal BST.

Medium Unique Paths LC 62 11 min Medium Longest Common Subsequence LC 1143 10 min Medium Best Time to Buy and Sell Stock with Cooldown LC 309 11 min Medium Coin Change II LC 518 11 min Medium Target Sum LC 494 11 min Medium Interleaving String LC 97 10 min Hard Longest Increasing Path in a Matrix LC 329 12 min Hard Distinct Subsequences LC 115 11 min Medium Edit Distance LC 72 11 min Hard Burst Balloons LC 312 12 min Hard Regular Expression Matching LC 10 12 min

Where top-down beats bottom-up

Unusually, two questions are better memoised than tabulated:

Question 7 — tabulating needs cells in increasing value order, so you'd sort all m·n of them at O(m·n log(m·n)). The DFS discovers a valid order for free.

Question 11 — the lookahead at p[j+1] reads naturally forwards; bottom-up must look backwards at p[j-1] and p[j-2] and seed row 0 by hand.

The traps

Trap	Symptom
Zero base cases in Edit Distance (Q9)	`("abc","")` returns 0 instead of 3
Not seeding row 0 in regex (Q11)	*`("", "a")` returns false**
Putting the skip in an `else` (Q8)	`"rabbbit"`→`"rabbit"` returns 1, not 3
Advancing the pattern on star-match (Q11)	`*` becomes "exactly one"
Swapping insert and delete (Q9)	Plausible table, wrong on asymmetric input
Wrong loop nesting (Q4)	Counts permutations instead of combinations
Ascending in 0/1 knapsack (Q5)	Each number signed twice
Missing `\|target\| > total` (Q5)	Negative array size — a crash, not a wrong answer
Adding a `visited` array (Q7)	Breaks memo reuse across starting cells
Tracking `k` separately (Q6)	`100×100×200` table, mostly unreachable
Asking "which bursts first" (Q10)	Subproblems interact; no DP possible

Verification

Every snippet compiled and cross-checked against an independent implementation — 3,200+ randomized cases:

Q1 across the DP, the recursion and the closed-form binomial
Q8 across the 2-D table, the rolled row and the recursion
Q9 across 2-D and rolled, plus symmetry (d(a,b) == d(b,a)) asserted on every case
Q10 against every-burst-order brute force — O(n!) on small inputs
Q11 against the recursive matcher on randomly generated patterns

Two deliberately-broken variants confirm the headline traps:

omitting Edit Distance's edge base cases returns 0 for ("abc", "") where the answer is 3
omitting regex's row-0 seeding returns false for ("", "a*")