2-D Dynamic Programming

When you need two dimensions

If a subproblem is identified by two indices — a cell in a grid, a pair of positions in two strings, or a (start, end) interval — the DP table is 2-D: dp[i][j]. The method is the same as 1-D (define the state, write the transition, base cases, optimize), just over a grid of states.

Grid paths

Each cell combines the cells it can come from:

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]      # first row/col = 1 (one way)
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]   # from above or left
    return dp[m-1][n-1]

Same shape: Minimum Path Sum, Unique Paths II (obstacles → 0), Maximal Square, Dungeon Game (fill backwards), Cherry Pickup (two agents → higher-dimensional state).

Two-sequence alignment (the big family)

dp[i][j] = the answer for the first i of A and first j of B. The transition compares A[i-1] and B[j-1]:

def lcs(a, b):
    dp = [[0] * (len(b)+1) for _ in range(len(a)+1)]   # padded row/col of 0s
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1            # extend the match
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # drop from one side
    return dp[-1][-1]

Powers Longest Common Subsequence, Edit Distance (min insert/delete/replace), Distinct Subsequences, Interleaving String, Regular Expression / Wildcard Matching (where the transition branches on *).

Knapsack as 2-D

The 0/1 knapsack and its relatives are dp[item][capacity]:

def can_partition(nums):                # subset summing to total/2?
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    dp = [False] * (target + 1); dp[0] = True
    for x in nums:                       # items outer
        for c in range(target, x - 1, -1):   # capacity backward → use each item once
            dp[c] = dp[c] or dp[c - x]
    return dp[target]

Conceptually 2-D (item × capacity), rolled to 1-D by iterating capacity backward. Relatives: Target Sum, Coin Change II (forward loop = unbounded), 0/1 Knapsack.

Interval DP

State dp[i][j] over a range [i, j], built from smaller ranges — for problems where you choose a split/last action within a range: Matrix Chain Multiplication, Burst Balloons, Longest Palindromic Subsequence, Stone Game. Iterate by increasing interval length so sub-intervals are ready.

Practical tips

• Pad the table with a base-case row/column (zeros/identity) to avoid index-bound checks.
• Roll to O(n) — many grid/two-sequence DPs read only the previous row, so two rows (or one, carefully) suffice. Get it correct as a full table first, then optimize.
• Reconstruct the path — walk back through dp from the end, choosing the predecessor that produced each value (needed for “return the actual subsequence/alignment”).
• Direction matters — some grids fill backward (Dungeon Game); interval DP fills by length.

Pitfalls

• Off-by-one between string index and dp index (A[i-1] for dp[i]).
• Premature space optimization — collapse to rolling arrays only after the 2-D logic is verified.
• Wrong iteration order — knapsack capacity direction, interval-length ordering.

Choosing in an interview

• Paths/areas in a grid → dp[i][j] from neighbors.
• Compare/transform two sequences → alignment DP.
• Items × capacity (subset-sum/knapsack) → knapsack DP (mind the loop direction).
• Optimal split over a range → interval DP (by length).

Define dp[i][j] in words and the transition before coding — 2-D DP rewards a precise state.