Dynamic programming on sequences, grids and knapsacks

Why it matters

Once one-dimensional DP is comfortable, most harder DP questions turn out to be variations of a handful of two-dimensional templates. Interviewers use them to test whether you can generalize a recurrence, keep indices straight across two inputs, and save memory without corrupting values you still need. The templates matter beyond interviews too: edit distance and alignment underlie diffing and fuzzy matching, knapsack-style DPs appear in budgeted selection and resource allocation, and interval DPs in parsing and optimal ordering.

Core ideas

Two sequences. Let the state be a pair of prefix lengths (i, j). For longest common subsequence: if a[i-1] == b[j-1], then dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Edit distance uses the same table: dp[i][j] is the minimum of dp[i-1][j] + 1 (delete), dp[i][j-1] + 1 (insert) and dp[i-1][j-1] plus 0 for a match or 1 for a replacement, with base cases dp[i][0] = i and dp[0][j] = j. Prefix lengths instead of indices give a natural empty row and column and remove most off-by-one errors. Time and space are O(nm).

Grids. With right and down moves, dp[r][c] depends on the cell above and the cell to the left. Initialize the first row and column carefully: after an obstacle in the first row, every later cell in that row is unreachable. If moves can go in all four directions, dependencies form cycles and the problem is a shortest-path search, not a DP.

0/1 knapsack. dp[i][w] is the best value using the first i items with capacity w: either skip item i, giving dp[i-1][w], or take it once, giving dp[i-1][w - weight] + value. With a single array indexed by capacity, iterate w from high to low so that dp[w - weight] still holds the previous item's value when it is read; iterating upward would let the same item be taken twice. Subset sum and equal-sum partition are the boolean version.

Unbounded knapsack. Items can be reused, so dp[w] takes the best over items of dp[w - weight] + value, and the single-array loop runs upward: reading the already updated dp[w - weight] is exactly what allows reuse.

Combinations versus ordered sequences. When counting ways to reach an amount, putting the coin loop outside the amount loop counts each multiset once; putting the amount loop outside counts ordered sequences. Decide which one the problem asks for before choosing.

Interval DP. For problems such as bursting balloons or optimal parenthesization, let dp[l][r] be the best result for the interval and choose the element handled last (or the split point) inside it. Evaluate by increasing interval length so every sub-interval is ready; this is typically O(n^3).

Pseudo-polynomial time. Knapsack in O(nW) is polynomial in the numeric value W, not in the input size, since W takes only about log W bits to write. It is fast for small capacities and hopeless for capacities near 10^9; then consider a state indexed by value instead of weight, meet in the middle, or approximation.

Memory and reconstruction. Rolling two rows, or one row with the correct direction, cuts O(nm) memory to O(m). To recover an alignment or a chosen item set, keep the full table or parent choices; Hirschberg's divide-and-conquer method recovers an alignment in linear space (deep level only).

Common misconceptions

• "0/1 and unbounded knapsack need different code." With one array, only the direction of the capacity loop differs, and that direction decides whether an item can be reused.
• "Loop order never matters in counting DPs." Swapping the coin and amount loops switches between counting combinations and counting ordered sequences.
• "Knapsack is polynomial." O(nW) is pseudo-polynomial; with W near 10^9 it is unusable.
• "Edit distance needs special cases for empty strings." With prefix-length states the empty row and column are the base cases; no extra branches are needed.
• "Every grid path problem is a DP." Only when moves create no cycles, as with right and down only; otherwise use BFS or Dijkstra.

How to approach it

Name the template first (two prefixes, a cell, an item and a capacity, an interval), then write the state in words and the case analysis on the last decision. Fill a tiny table, about 3 by 3, by hand to confirm the base cases and the direction of dependencies before coding. Compress memory only after the full table works, and say which way the loops run and why. Graduate interviews usually stop at a correct O(nm) table; mid and senior interviews more often ask for reconstruction, the memory optimization, or how the approach scales as capacities or string lengths grow.