Dynamic programming: 2D

When one index isn't enough

2D DP shows up whenever the state needs two pieces of changing information to describe it — a position in a grid (row, col), two strings being compared (index into each), or an item index plus a remaining budget. The recipe from the 1D chapter doesn't change: define the state, find the recurrence, pick a base case, fill in order. Only now the table has two axes.

Grid paths — the most visual entry point

// unique paths from top-left to bottom-right, moving only right or down
function uniquePaths(rows, cols) {
  const dp = Array.from({ length: rows }, () => new Array(cols).fill(1)); // first row/col = 1 way

  for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      dp[r][c] = dp[r - 1][c] + dp[r][c - 1]; // from above, or from the left
    }
  }
  return dp[rows - 1][cols - 1];
}

Comparing two strings — the other common shape

Longest Common Subsequence: dp[i][j] = the LCS length using the first i characters of one string and the first j of the other.

function longestCommonSubsequence(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[a.length][b.length];
}

The 0/1 Knapsack shape — item index vs. remaining capacity

// dp[i][w] = best value using the first i items, with capacity w remaining
function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w]; // option 1: don't take item i
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1] // option 2: take it
        );
      }
    }
  }
  return dp[n][capacity];
}

Every "at most one of each item, maximize value under a budget" problem is this exact shape — the two options at each cell (skip it / take it) are the same two-branch decision as the LCS match/mismatch above, just applied to a different pair of dimensions.

Edit Distance — arguably the single most-asked 2D DP question

Minimum number of insert/delete/replace operations to turn one string into another. Same LCS-style grid, but now three branches instead of two, because a mismatch has three possible fixes.

function minDistance(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));

  // base cases: turning "" into b (all inserts) or a into "" (all deletes)
  for (let i = 0; i <= a.length; i++) dp[i][0] = i;
  for (let j = 0; j <= b.length; j++) dp[0][j] = j;

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // characters already match — no operation needed
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // delete from a
          dp[i][j - 1],     // insert into a
          dp[i - 1][j - 1]  // replace in a
        );
      }
    }
  }
  return dp[a.length][b.length];
}

This is LCS's structure with the mismatch branch upgraded from "pick the better of two neighbors" to "pick the best of three, plus a cost of 1" — once you've internalized LCS, Edit Distance is a small, specific variation, not a new problem from scratch.

Palindrome DP — a different kind of two-dimensional state

Here both dimensions describe the same string — a start index and an end index — rather than two different strings. "Is s[i..j] a palindrome?" depends on whether the outer characters match and the inside is also a palindrome, which means filling the table by increasing substring length, not row by row.

// dp[i][j] = true if s[i..j] (inclusive) is a palindrome
function longestPalindromicSubstring(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));
  let start = 0, maxLen = 1;

  for (let i = 0; i < n; i++) dp[i][i] = true; // every single character is a palindrome

  // fill by SUBSTRING LENGTH, not by row — a length-3 answer needs the length-1 answer inside it already computed
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (s[i] !== s[j]) continue;
      dp[i][j] = len === 2 || dp[i + 1][j - 1]; // outer chars match AND inside is a palindrome
      if (dp[i][j] && len > maxLen) { start = i; maxLen = len; }
    }
  }
  return s.slice(start, start + maxLen);
}

Space optimization: do you really need the whole grid?

If dp[i][...] only ever depends on row i-1 (never row i-2 or earlier), you can collapse the table to two 1D rows — or even one row updated in place, for knapsack-style problems traversed right to left. This turns O(rows × cols) space into O(cols), the same "space-optimized" move as the end of the 1D chapter.

Recognizing 2D over 1D

• Two sequences are being compared against each other (strings, arrays) → likely LCS-shaped
• "Minimum operations to transform one string into another" → Edit Distance's three-branch variant of LCS
• Movement on an actual grid → likely paths-shaped
• One sequence plus a constraint that itself has a range of values (weight, budget, count) → likely knapsack-shaped
• "Is this substring/subsequence a palindrome" → fill by increasing length, not row by row
• If the state needs a third piece of information, you're not stuck — extend to a 3D table (or a map keyed by a tuple) using the exact same recipe

See the table fill

Watch which cells each new cell reads. On a match it reaches diagonally; otherwise it takes the better of above and left. That dependency pattern is the whole recurrence.