Two Dimensions: LCS, Knapsack, Edit Distance

When one index is not enough

In 1-D DP a single quantity shrinks toward a base case: the step number, the amount left, the position in one string. Some problems have two independent quantities shrinking at once — your position in string A and your position in string B, or the item you are considering and the capacity you have left, or a row and a column in a grid. One index cannot describe such a subproblem. Two can: the state becomes dp[i][j], and the table becomes a 2-D grid.

The recipe is unchanged from 1-D: define the state in one English sentence, write the recurrence, seed the base cases, fill in dependency order. What is new is the geometry. Almost every 2-D recurrence reads from at most three neighbors — the cell above (dp[i-1][j]), the cell to the left (dp[i][j-1]), and the diagonal (dp[i-1][j-1]). Each feeder cell is a choice, and what the choice means depends on the family.

Family 1: grid paths

Unique Paths: a robot walks from the top-left of a grid to the bottom-right, moving only right or down. How many routes? State: dp[i][j] = number of ways to reach cell (i, j). The last move into any cell came from above or from the left, so:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Base cases: the whole first row and first column are 1 (only one straight path reaches them). For a 3×3 grid:

Six paths. Here top and left mean "where I physically came from", and there is no diagonal.

Family 2: aligning two strings (LCS)

Longest Common Subsequence: given s = "abcde" and t = "ace", find the longest sequence of characters appearing in both, in order (not necessarily adjacent). State: dp[i][j] = LCS length of the first i characters of s and the first j characters of t. Note the off-by-one convention: dp[i][j] covers prefixes of length i and j, so the table is (m+1)×(n+1) and row/column 0 mean "empty prefix" and hold 0.

The recurrence looks at the last characters s[i-1] and t[j-1]:

if s[i-1] == t[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1        # consume both — diagonal
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # drop one or the other

Now the three feeders have precise meanings: diagonal = match both last characters and extend, top = ignore the last character of s, left = ignore the last character of t. Filled for "abcde" vs "ace":

Answer: 3 ("ace"). Walking the table backwards from the corner — following diagonals at matches — recovers the actual subsequence.

Family 3: edit distance

Same shape, different meaning. dp[i][j] = fewest edits (insert, delete, replace one character) to turn the first i characters of s into the first j characters of t. If the last characters match, the diagonal is free. Otherwise every feeder is one of the three edits, plus cost 1:

if s[i-1] == t[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(dp[i-1][j],    # delete from s
                       dp[i][j-1],    # insert into s
                       dp[i-1][j-1])  # replace

The trap here is the base row and column: they are not zero. Turning i characters into the empty string takes i deletions, so dp[i][0] = i; likewise dp[0][j] = j. For "horse" → "ros" the corner comes out to 3.

Family 4: items plus capacity (knapsack)

The second dimension does not have to be a string — it can be a budget. 0/1 knapsack: each item has a weight and value, use each at most once, maximize value within capacity C. dp[i][c] = best value using the first i items with capacity c; each item is taken or skipped. Since row i reads only row i-1, one array suffices — but then loop direction becomes the whole ballgame:

for weight, value in items:
    for cap in range(C, weight - 1, -1):   # DOWNWARD: each item once
        dp[cap] = max(dp[cap], dp[cap - weight] + value)

Looping capacity downward means dp[cap - weight] still reflects the previous item row, so an item cannot feed into itself. Loop upward and the item can be reused — which is exactly what unbounded knapsack wants. Coin Change II (count the ways to make an amount with unlimited coins) is unbounded, plus one more subtlety — coins on the outer loop so each combination is counted once, not once per ordering:

dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:                     # coins outer = combinations
    for a in range(coin, amount + 1):  # upward = unlimited reuse
        dp[a] += dp[a - coin]

The loop-direction and loop-order pair is the single most-tested detail in this module.

The odd sibling: interval DP

One more family indexes the table differently: dp[i][j] describes the answer for the substring or subarray from i to j. Longest Palindromic Subsequence and Burst Balloons live here. The recurrence combines smaller intervals inside [i, j] — for Burst Balloons, pick which balloon k pops last in the interval, so the two sides are fully independent:

dp[i][j] = max(dp[i][k] + dp[k][j] + a[i] * a[k] * a[j] for k in i+1..j-1)

Interval DP cannot fill in reading order: dp[i][j] needs shorter intervals, not cells above and left. Fill by increasing interval length — all length-2 intervals, then length-3, and so on — or memoize and let recursion sort out the order.

Space: rolling rows

Whenever a row depends only on the previous row (grid paths, LCS, knapsack), you can keep two rows instead of the whole table — or one row plus a saved diagonal variable — cutting O(m·n) space to O(min(m, n)). Say this out loud in interviews even if you code the full table; it is cheap credit. Interval DP cannot roll: it reaches back to arbitrary shorter intervals.

Recognition signals

Reach for 2-D DP when you see: two strings compared ("common subsequence", "edit distance", "interleaving", "distinct subsequences"), items plus a budget ("target sum", "number of combinations"), paths in a grid with counts or costs, or answers about every substring/subinterval (palindromes, balloons). The confirming question: are there two independent quantities that both shrink toward a base case? If yes, name dp[i][j] in a sentence before writing anything else.