2D DP: Grids, Strings, Knapsack

Some problems need two numbers to describe a subproblem, so the table becomes a grid dp[i][j]. Three families:

• Grids: dp[r][c] = answer for reaching cell (r, c)
• Two strings: dp[i][j] = answer for the prefixes a[:i] and b[:j]
• Items + capacity (knapsack): dp[i][s] = answer using the first i items with budget s

The recipe doesn't change. There are just more cells, and you fill them row by row.

Grids: Unique Paths. A robot starts top-left of an m × n grid and moves only right or down. How many paths reach the bottom-right? The last move into a cell came from above or from the left:

dp[r][c] = dp[r-1][c] + dp[r][c-1]
first row and first column: 1 (a straight line)

Rolling a row. Each row only reads the row above it, so keep one list and update it in place: before row[c] += row[c - 1], row[c] still holds the value from above and row[c - 1] is already the new value to the left. Space drops from O(m·n) to O(n).

Two strings: Longest Common Subsequence. Compare prefixes a[:i] and b[:j] and look at their last characters:

if a[i-1] == b[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1        # use both
else:
    dp[i][j] = max(dp[i-1][j],         # drop from a
                   dp[i][j-1])         # drop from b

Row 0 and column 0 stand for the empty string (LCS 0). For a = "abcde", b = "ace":

      ""  a  c  e
  ""   0  0  0  0
  a    0  1  1  1
  b    0  1  1  1
  c    0  1  2  2
  d    0  1  2  2
  e    0  1  2  3

Edit Distance uses the same grid. dp[i][j] = fewest edits turning a[:i] into b[:j]. If the last characters match, it costs nothing: dp[i-1][j-1]. Otherwise pay 1 for the best of:

• delete a[i-1] → dp[i-1][j]
• insert b[j-1] → dp[i][j-1]
• replace a[i-1] with b[j-1] → dp[i-1][j-1]

Base cases: dp[i][0] = i (delete everything), dp[0][j] = j (insert everything).

0/1 knapsack: subset sum. Can some of the numbers (each used at most once) add up to target? State dp[i][s]: can the first i numbers make sum s? Number i is either skipped or used:

dp[i][s] = dp[i-1][s] or dp[i-1][s - x]

Every row only reads the row above, so roll it into one list dp[s]. The catch: loop s downwards. Going upwards, dp[s - x] would already include x from this same row, so x could be used twice. That turns 0/1 knapsack into unbounded knapsack (Coin Change) by accident.