Pattern 14 of 18 · Dynamic Programming

2-D Dynamic Programming

Extend DP across two dimensions — grids, strings, and sequences compared pairwise.

The same DP idea as 1-D, but the state depends on two indices — often two positions in a grid, or a position in each of two sequences being compared.

Key concepts

  • State is typically `dp[i][j]` — e.g. "the answer using the first `i` characters of one string and the first `j` of another," or "the best path to cell (i, j)."
  • Base cases usually live along the first row and/or first column of the DP table.
  • Fill order matters — each cell should only depend on cells already computed.

When to use it

  • You're comparing two sequences (finding a longest common subsequence, edit distance).
  • You're computing paths or optimal values across a 2-D grid.

Tips

  • Draw a small grid by hand for the base cases — it makes the recurrence direction obvious.
  • Many 2-D DP problems can be space-optimized to O(n) by keeping only the previous row.
  • Watch your indices carefully — off-by-one errors are the most common bug when the table has an extra row/column for empty-prefix base cases.

Practice problems (11)

Blind 75 (2):

More from Blind 150 (9):

← 1-D Dynamic ProgrammingGreedy →

See the full roadmap →