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) {
  if (rows < 1 || cols < 1) return 0;
  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];
}

Dry run: uniquePaths(3, 4) — the grid in the figure above

Row 0 and column 0 never get computed — they start (and stay) at 1, because there's only one way to reach any cell along the top or left edge: keep going the one direction that stays on the grid. The answer, dp[2][3] = 10, matches the bottom-right cell in the figure.

Obstacles and costs: Unique Paths II and Minimum Path Sum

Two small changes to the grid recurrence cover most of the grid questions you will be asked. Put walls in some cells, and the first row and column stop being all 1s. Put a cost on every cell, and the question changes from "how many routes" to "which route is cheapest". The recurrence still looks at the same two neighbours, above and left. What changes is how it combines them and what the edges hold.

Unique Paths II: some cells are walls

dp[r][c] is still the number of routes from the start that end on (r, c). A wall has no routes ending on it, because nobody can stand there, so it holds 0. And because every route into a cell comes through the cell above or the cell to the left, that 0 flows forward by itself: the cells to its right and below simply get nothing from it.

The version at the top of this chapter filled the first row and column with 1s, which is only right when nothing blocks them. With a wall in the first row, every cell to the right of it is unreachable, and those 1s would lie. So give every cell the same rule, count a neighbour that is off the grid as 0 routes, and seed only the start.

function uniquePathsWithObstacles(grid) {
  const rows = grid.length, cols = grid[0].length;
  const dp = Array.from({ length: rows }, () => new Array(cols).fill(0));

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1) continue; // a blocked cell stays 0: no path passes through it
      if (r === 0 && c === 0) { dp[r][c] = 1; continue; } // standing on the start is one way
      const fromAbove = r > 0 ? dp[r - 1][c] : 0;
      const fromLeft = c > 0 ? dp[r][c - 1] : 0;
      dp[r][c] = fromAbove + fromLeft;
    }
  }
  return dp[rows - 1][cols - 1];
}

Dry run: a 3 by 3 grid with a wall in the middle

grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]], where 1 is a wall

The top row and left column are all 1s here because nothing blocks them. The centre is a wall and stays 0. The cell right of the centre is dp[0][2] + dp[1][1] = 1 + 0 = 1, the cell below it is dp[1][1] + dp[2][0] = 0 + 1 = 1, and the corner adds the two: dp[1][2] + dp[2][1] = 1 + 1 = 2. Both routes go around the wall, one over the top and one underneath.

Minimum Path Sum: every cell has a cost

Now each cell has a cost and you want the cheapest right-and-down route from the top-left to the bottom-right. Let dp[r][c] be the cheapest cost of a route from the start to (r, c), including the cost of (r, c) itself. The last step of any route into that cell came from above or from the left, so the cheapest route is the cell's own cost plus the cheaper of the two arrivals.

function minPathSum(grid) {
  const rows = grid.length, cols = grid[0].length;
  const dp = Array.from({ length: rows }, () => new Array(cols).fill(0));

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (r === 0 && c === 0) { dp[r][c] = grid[0][0]; continue; }
      const fromAbove = r > 0 ? dp[r - 1][c] : Infinity; // off the grid counts as unreachable
      const fromLeft = c > 0 ? dp[r][c - 1] : Infinity;
      dp[r][c] = grid[r][c] + Math.min(fromAbove, fromLeft);
    }
  }
  return dp[rows - 1][cols - 1];
}

The off-grid neighbours are Infinity rather than 0 on purpose. A top-row cell has no cell above it, and 0 would pretend that a free route arrives from there, so the minimum would pick it every time and quietly drop the cost of everything to its left. Infinity can never be the minimum, which is the right way to say "that arrival does not exist".

Dry run: [[1, 3, 1], [1, 5, 1], [4, 2, 1]]

The answer, dp[2][2] = 7, is the route right, right, down, down, which costs 1 + 3 + 1 + 1 + 1. The 5 in the middle is the expensive cell and the table routes around it: dp[1][1] = 5 + min(4, 2) = 7, and neither neighbour that could use it prefers it. Each cell costs O(1), so the whole table is O(rows × cols) time and space. Row r reads only row r - 1, so keeping one row (or writing over a copy of the grid) takes the space to O(cols), at the price of losing the table you would need to rebuild the route.

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.

Getting the answer back out, not only its length

The usual follow-up to "return the length" is "now return the actual subsequence", or "list the edits", or "which items did you pack". You do not need a second algorithm. Every cell's value was chosen from specific neighbours, and that choice is still visible in the numbers. Start at the answer cell and ask, at each cell, "which neighbour explains this value?". Step to it, note what that step meant, and repeat until you reach the padding. You collect the choices from the end to the start, so reverse them at the end.

The LCS string

When the two characters match, the cell was defined as the diagonal plus one, so stepping diagonally is always a valid explanation and that character belongs to the answer. When they do not match, the cell was the larger of above and left, so step toward the larger one. The character you stepped past is not used.

function lcsString(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++) {
      dp[i][j] = a[i - 1] === b[j - 1]
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }

  const picked = [];
  let i = a.length, j = b.length;
  while (i > 0 && j > 0) { // walk from the answer cell back toward the padding
    if (a[i - 1] === b[j - 1]) {
      picked.push(a[i - 1]); // a match is part of the answer: step diagonally
      i--; j--;
    } else if (dp[i - 1][j] >= dp[i][j - 1]) {
      i--; // the value came from above, so a[i - 1] is not used
    } else {
      j--; // the value came from the left, so b[j - 1] is not used
    }
  }
  return picked.reverse().join(""); // collected back to front
}

Dry run: lcsString("ABCB", "BDCAB")

The table first, with the rows labelled by a and the columns by b.

The walk ends at (1, 0), which sits on the padding column, so the loop stops. The picks were collected back to front, B then C then B, and the reversal gives "BCB", which has the length 3 that the corner cell promised. When the two neighbours tie, either step is valid; >= prefers going up, and the other choice would return a different, equally long subsequence on inputs that have more than one.

The edit script

The same walk works for Edit Distance, with more cases. At a cell, first check for a match, because a match was defined as a free diagonal copy. If there is no match, compare the cell with each neighbour plus 1 and step to one that fits. The step you take is the operation.

function editScript(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
  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++) {
      dp[i][j] = a[i - 1] === b[j - 1]
        ? dp[i - 1][j - 1]
        : 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
    }
  }

  const steps = [];
  let i = a.length, j = b.length;
  while (i > 0 || j > 0) {
    if (i > 0 && j > 0 && a[i - 1] === b[j - 1]) {
      steps.push("keep " + a[i - 1]);
      i--; j--;
    } else if (i > 0 && j > 0 && dp[i][j] === dp[i - 1][j - 1] + 1) {
      steps.push("replace " + a[i - 1] + " with " + b[j - 1]);
      i--; j--;
    } else if (i > 0 && dp[i][j] === dp[i - 1][j] + 1) {
      steps.push("delete " + a[i - 1]);
      i--;
    } else {
      steps.push("insert " + b[j - 1]); // only the left neighbour can explain the cell now
      j--;
    }
  }
  return steps.reverse();
}

Dry run: editScript("horse", "ros")

From the corner dp[5][3] = 3: e and s differ, and the only neighbour that explains the 3 is the cell above, dp[4][3] = 2, plus 1, so the step is "delete e". Then s matches s: keep. Then r against o: the cell above, dp[2][2] = 1, plus 1 gives the current 2, so delete r. Then o matches: keep. The last cell, dp[1][1] = 1, is the diagonal 0 plus 1: replace h with r. Reversed, the script is: replace h with r, keep o, delete r, keep s, delete e, and three of those five steps cost something, which is the 3 in the corner. When two operations would both explain a cell, the order of the if checks decides which script you get; any of them is optimal.

The packed items in a knapsack

For the knapsack table, ask at each row whether the value changed when that item arrived. If dp[i][w] equals dp[i - 1][w], item i was not needed to reach it, so skip it. If it differs, the item must have been taken: record it and move to the capacity that was left before it, w - weights[i - 1].

function knapsackItems(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];
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
      }
    }
  }

  const taken = [];
  let w = capacity;
  for (let i = n; i >= 1; i--) {
    if (dp[i][w] !== dp[i - 1][w]) { // the value changed when item i arrived, so it was taken
      taken.push(i - 1);
      w -= weights[i - 1];
    }
  }
  return { best: dp[n][capacity], items: taken.reverse() };
}

Dry run: weights [1, 3, 4, 5], values [1, 4, 5, 7], capacity 7

Start at dp[4][7] = 9. The row above is also 9, so the fourth item is skipped. At row 3, dp[3][7] = 9 but the row above has 5, so item index 2 (weight 4, value 5) is taken and the capacity drops to 3. At row 2, dp[2][3] = 4 against 1 above, so item index 1 (weight 3, value 4) is taken and the capacity drops to 0. Row 1 is 0 against 0, so the first item is skipped. The result is items 1 and 2, weight 3 + 4 = 7 and value 4 + 5 = 9, matching the corner. If two packings tie for the best value, this walk returns one of them.

Longest common substring: the table that resets to zero

A substring cannot skip characters, so the LCS table gives the wrong answer here. "ABXC" and "ABYC" have a longest common subsequence of length 3 ("ABC") but a longest common substring of length 2 ("AB"). The definition has to change. Let dp[i][j] be the length of the common run that ends exactly at a[i - 1] and b[j - 1]. If those two characters match, the run that ended at the previous pair grows by one: dp[i - 1][j - 1] + 1. If they differ, there is no run ending here, so the cell is 0, not the larger of two neighbours.

function longestCommonSubstring(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
  let bestLen = 0, bestEnd = 0; // bestEnd is an index into a, one past the last character

  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; // the run ending at both previous characters grows by one
        if (dp[i][j] > bestLen) { bestLen = dp[i][j]; bestEnd = i; }
      } // a mismatch leaves 0: a substring cannot skip a character
    }
  }
  return a.slice(bestEnd - bestLen, bestEnd);
}

Dry run: longestCommonSubstring("abcde", "zbcdf")

The run grows along the diagonal: b gives 1, c gives 2, d gives 3, and then e against f breaks it back to 0. The answer sits in the middle of the table, not in the corner. The corner here is 0, and reading it would be wrong, because a run can end anywhere. That is why the code tracks the best length and where it ended while it fills the table, and slices the answer out of a at the end.

Both tables read only the previous row, so the length alone fits in two rows, as in the space section below. For strings long enough that O(m × n) is too slow, the faster route is hashing with a binary search on the length, which the string algorithms chapter covers.

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 every cell must be filled after dp[i+1][j-1]. Filling by increasing substring length does that, and so does filling the rows from the bottom up; filling the rows from the top down does not.

// 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 — a length-3 answer needs the length-1 answer inside it already computed (rows bottom-up also works; rows top-down does not)
  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);
}

Longest palindromic subsequence: the same interval table, a different rule

The palindrome section above asked a yes-or-no question about every substring. Here you may skip characters, and you want the length of the longest palindrome you can read off. The state is the same pair of indices, dp[i][j] for the part of the string from i to j, but the cell now holds a length. Look at the two ends. If s[i] and s[j] are equal, both can wrap the best palindrome found strictly inside, which adds 2. If they differ, at least one of them is unused, so the answer is the better of dropping the left end or dropping the right end.

function longestPalindromeSubseq(s) {
  const n = s.length;
  if (n === 0) return 0;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));

  for (let i = n - 1; i >= 0; i--) { // rows bottom-up: row i + 1 is finished before row i
    dp[i][i] = 1;
    for (let j = i + 1; j < n; j++) {
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2; // wrap the best palindrome of the inside
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // drop one end
      }
    }
  }
  return dp[0][n - 1];
}

Dry run: longestPalindromeSubseq("bbbab")

Only the cells on and above the diagonal mean anything. Row 4 is a single character, 1. In row 3, s[3] = a and s[4] = b differ, so dp[3][4] = max(dp[4][4], dp[3][3]) = 1. The corner works from the ends: s[0] = b and s[4] = b match, so dp[0][4] = dp[1][3] + 2 = 2 + 2 = 4, the palindrome bbbb. For two neighbours that match, such as j = i + 1, the code reads dp[i + 1][j - 1], which is a cell below the diagonal. It was never written, so it still holds 0, and 0 is exactly the right length for an empty inside.

Two facts help when you are stuck. The length equals the longest common subsequence of s and its own reverse, so you can reuse your LCS code. And the fewest characters you would have to insert to turn s into a palindrome is s.length minus this number, because the characters that are not part of the longest palindromic subsequence are the ones that need a mirror. As with the palindrome table above, the fill order matters: the loop runs i from the bottom up, so row i + 1 is complete before row i starts. Time and space are O(n²), and since row i reads only itself and row i + 1, two rows are enough for the length.

Counting instead of optimizing: distinct subsequences, interleaving string and target sum

Some questions ask how many ways, or whether it is possible, rather than how good. The table is the same, and only the cell's meaning and the operator change. When the options at a cell are exclusive and cover everything, the number of ways is the sum of the ways under each option, where an optimization used Math.max. When the question is a yes or no, the sum becomes an OR. The part to get right is the base case: the count for the empty case is usually 1, not 0, because there is exactly one way to build nothing, which is to choose nothing.

Distinct Subsequences: how many ways does t appear inside s?

Let dp[i][j] be the number of ways that the first j characters of t appear as a subsequence of the first i characters of s. Look at the last character of that prefix of s. Either it is not used, which leaves dp[i - 1][j] ways, or it is used to match t[j - 1], which is only possible when the two are equal and then leaves dp[i - 1][j - 1] ways. Every way falls under exactly one of those, so you add them. The base is dp[i][0] = 1: the empty target appears once in any prefix. dp[0][j] for j > 0 stays 0, because an empty source cannot spell anything.

function numDistinct(s, t) {
  const m = s.length, n = t.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = 1; // the empty target forms one way from any prefix

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = dp[i - 1][j]; // ways that do not use s[i - 1]
      if (s[i - 1] === t[j - 1]) {
        dp[i][j] += dp[i - 1][j - 1]; // plus ways that spend s[i - 1] on t[j - 1]
      }
    }
  }
  return dp[m][n];
}

Dry run: numDistinct("babgbag", "bag")

The answer is 5. Read the last column to see why: the first g (at index 3) lets "bag" be formed 1 way. The second g (index 6) adds the 4 ways to spell "ba" in the six characters before it, giving 1 + 4. As index pairs, the five ways are (0, 1, 3), (0, 1, 6), (0, 5, 6), (2, 5, 6) and (4, 5, 6). The counts can grow past what a double holds exactly, so check whether the problem guarantees a small answer or asks for a remainder.

Interleaving String: can s3 be woven from s1 and s2?

Here dp[i][j] is true if the first i characters of s1 and the first j of s2 can be woven, keeping each string's own order, into the first i + j characters of s3. The last of those i + j characters came from one of the two strings. If it came from s1, then s1[i - 1] must equal it and the smaller state (i - 1, j) must be true. If it came from s2, the symmetrical test on (i, j - 1) applies. Either is enough, so you OR them. Check the lengths first: if s1 and s2 together are not as long as s3, the answer is false at once, and without the check the indexing would read past the end of s3.

function isInterleave(s1, s2, s3) {
  const m = s1.length, n = s2.length;
  if (m + n !== s3.length) return false;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true; // zero characters of each build zero characters of s3

  for (let i = 0; i <= m; i++) {
    for (let j = 0; j <= n; j++) {
      if (i === 0 && j === 0) continue;
      const next = s3[i + j - 1]; // the character of s3 that this cell must place
      const viaS1 = i > 0 && dp[i - 1][j] && s1[i - 1] === next;
      const viaS2 = j > 0 && dp[i][j - 1] && s2[j - 1] === next;
      dp[i][j] = viaS1 || viaS2;
    }
  }
  return dp[m][n];
}

Dry run: s1 = "ab", s2 = "ac", s3 = "aacb"

T is true and F is false. The corner is true by the route (0,0), (1,0), (1,1), (1,2), (2,2). Reading s3 = a, a, c, b along it: a from s1, a from s2, c from s2, then b from s1. A greedy walk that just matches characters would fail on s3 = "acab": at the start both strings offer an a, and committing to s1 hits a dead end, while taking it from s2 works. The table keeps both options alive, which is why this needs DP and not two pointers.

Target Sum: reduce it to counting subsets

Put a plus or a minus in front of every number so that the total equals target, and count the ways. Split the numbers into the group that gets a plus, P, and the group that gets a minus, N. Then sum(P) - sum(N) = target, and sum(P) + sum(N) = total. Add the two equations and sum(P) = (total + target) / 2. So the question becomes: in how many ways can a subset of the numbers add up to exactly that goal? That is a knapsack-shaped table where the "value" is a count. If total + target is odd, or |target| is larger than total, the answer is 0 before any table is built.

function findTargetSumWays(nums, target) {
  const total = nums.reduce((sum, x) => sum + x, 0);
  if (Math.abs(target) > total || (total + target) % 2 !== 0) return 0;
  const goal = (total + target) / 2; // the sum the "plus" group must reach

  const n = nums.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(goal + 1).fill(0));
  dp[0][0] = 1; // no numbers and sum 0: one way, the empty group

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= goal; w++) {
      dp[i][w] = dp[i - 1][w]; // nums[i - 1] goes in the minus group
      if (nums[i - 1] <= w) {
        dp[i][w] += dp[i - 1][w - nums[i - 1]]; // or in the plus group
      }
    }
  }
  return dp[n][goal];
}

Dry run: nums = [1, 1, 1, 1, 1], target = 3

total = 5, so the plus group must sum to goal = (5 + 3) / 2 = 4

Row i counts the subsets of the first i ones that sum to each w, which is a binomial coefficient. The cell dp[5][4] = 5 is the number of ways to choose four of the five ones to be the plus group, so five different sign patterns reach 3. Notice that dp[i][0] is not always 1. When the input contains a 0, that number can go in either group without changing any sum, so the table doubles. For [0, 0, 1] and a target of 1 the column for w = 0 reads 1, 2, 4, 4 and the answer is 4. Setting dp[i][0] = 1 by habit would give the wrong answer here, and the code avoids it by starting w at 0 and applying the same rule to every cell.

This table keeps a row per number so you can see what each cell reads. Each row reads only the row above, and the one-row version, with the capacity loop running downward so a number is not used twice, is the subject of DP state machines and the knapsack family. Time and space here are O(n × goal), where goal is a value in the input rather than a count of items. That is a pseudo-polynomial cost, and it is only small when the numbers are.

Maximal Square: three neighbours and a minimum

Given a grid of "1" and "0" characters, find the area of the largest square made only of 1s. Checking every possible square from scratch repeats a lot of work, because a big square is made of smaller squares. So let dp[r][c] be the side of the largest all-1 square whose bottom-right corner is (r, c). A cell holding "0" has 0. For a cell holding "1", the claim is

dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1])

Why the smallest of the three? Suppose a square of side k ends at (r, c). Slide its frame one step up, one step left, and one step up-left: each of those three shifted squares has side k - 1 and is all 1s, so each neighbour is at least k - 1, and the minimum of the three is at least k - 1. In the other direction, let m be the minimum of the three. The square of side m + 1 ending at (r, c) is covered by the m-sided squares ending at the cell above, the cell to the left and the cell up-left, plus the cell itself, and all of those are 1s. So 1 + m is achievable, and nothing larger is. One neighbour with a short square, or a stray 0 in one of the three corners, caps the answer.

function maximalSquare(matrix) {
  const rows = matrix.length, cols = matrix[0].length;
  const dp = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0)); // padded row and column of 0
  let side = 0;

  for (let r = 1; r <= rows; r++) {
    for (let c = 1; c <= cols; c++) {
      if (matrix[r - 1][c - 1] === "1") { // the cells are the strings "1" and "0"
        dp[r][c] = 1 + Math.min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]);
        side = Math.max(side, dp[r][c]);
      }
    }
  }
  return side * side;
}

Dry run on a 4 by 5 grid

rows: "10100", "10111", "11111", "10010". The table has a padding row and column of 0, so the first printed row and column are the padding.

The largest value is 2, so the answer is 2 × 2 = 4. It first appears at dp[3][4]: the cell is a 1, and the cells above, to the left and up-left are 1, 1 and 1, so 1 + min(1, 1, 1) = 2. The cap shows at dp[3][2]: that cell is a 1 and its left and up-left neighbours are 1, but the cell directly above it is a 0, so the result is 1 + min(0, 1, 1) = 1 and no larger square can end there.

Pattern matching: wildcards and regular expressions

Does the whole string s match the pattern p? A prefix of the string and a prefix of the pattern are two independent positions, so this is a two-string table again. Let dp[i][j] be true when the first i characters of s match the first j characters of p. Two small pattern languages are asked about, and they differ in a way that matters.

• Wildcard: ? matches any single character, and * matches any sequence, including an empty one. The star stands on its own.
• Regular-expression subset: . matches any single character, and x* means zero or more copies of the preceding element x. The star only means something together with what is in front of it.

Wildcard: the star stands alone

An ordinary character or a ? uses up one character of each side, so dp[i][j] needs dp[i - 1][j - 1] to be true and the two characters to agree. A * has two options. It matches nothing, which leaves dp[i][j - 1], or it swallows s[i - 1] and stays available to swallow more, which leaves dp[i - 1][j]. The base row follows: an empty string matches a pattern prefix only if that prefix is all stars.

function isMatchWildcard(s, p) {
  const m = s.length, n = p.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true;
  for (let j = 1; j <= n; j++) dp[0][j] = dp[0][j - 1] && p[j - 1] === "*"; // only stars match nothing

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === "*") {
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; // the star matches empty, or swallows s[i - 1] and stays
      } else {
        dp[i][j] = (p[j - 1] === "?" || p[j - 1] === s[i - 1]) && dp[i - 1][j - 1];
      }
    }
  }
  return dp[m][n];
}

Dry run: isMatchWildcard("ab", "*b")

The star in column 1 matches the empty string (dp[0][1] is true), and it stays true after swallowing a and then b, which is the whole of column 1. Column 2 is the b: only the last row can use it, because b matches s[1] and dp[1][1], the string "a" against "*", is true. So the corner is true.

Regular expression: the star belongs to the character before it

Now x* is one unit, and the table has to treat it as a unit. At a star, look two columns back for the first option: dp[i][j - 2] means "use zero copies, as if the pair were not in the pattern". The second option is that x matches s[i - 1] and the pair stays to absorb possibly more, which leaves dp[i - 1][j]. Anything else is the plain rule from before. The base row changes too, because a*b* can match the empty string: dp[0][j] for a star is dp[0][j - 2].

function isMatch(s, p) {
  const m = s.length, n = p.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true;
  for (let j = 2; j <= n; j++) {
    if (p[j - 1] === "*") dp[0][j] = dp[0][j - 2]; // "a*b*" can match the empty string
  }

  const same = (ch, pc) => pc === "." || pc === ch;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === "*") {
        const zeroCopies = dp[i][j - 2]; // drop the "x*" pair altogether
        const oneMore = same(s[i - 1], p[j - 2]) && dp[i - 1][j]; // "x*" absorbs s[i - 1] and may absorb more
        dp[i][j] = zeroCopies || oneMore;
      } else {
        dp[i][j] = same(s[i - 1], p[j - 1]) && dp[i - 1][j - 1];
      }
    }
  }
  return dp[m][n];
}

Dry run: isMatch("aab", "a*b")

dp[1][2]: the star has already matched one a, because a matches s[0] and dp[0][2], the empty string against "a*", is true. dp[2][2] then reuses that: the same star takes the second a from dp[1][2]. The final b is an ordinary character that needs dp[2][2], which is true, and s[2] = b equal to p[2] = b, so the corner is true.

Russian Doll Envelopes: when sorting removes a dimension

An envelope fits inside another if both its width and its height are strictly smaller. Given a list of [width, height] pairs, find the longest chain of nesting envelopes. The first idea is a table over pairs of envelopes: sort them, let best[i] be the longest chain ending at envelope i, and compare it against every earlier one. That is O(n²) comparisons, too slow when n is in the tens of thousands, and no grid is involved at all. The "2D" is in the problem, not in the table.

The way out is to sort by width and leave only one dimension to worry about. After sorting by width ascending, any chain is a subsequence of the sorted list whose widths increase, so what remains is to make the heights strictly increase: the longest increasing subsequence of the heights. There is one trap. Two envelopes with the same width must never both be in a chain, but nothing in the sorted order stops an increasing run of heights from using both. The fix is to sort ties by height descending. Then envelopes of one width appear tallest first, so no increasing run can pick two of them.

For the increasing subsequence use the tails array. Let tails[k] be the smallest height that can end a chain of k + 1 envelopes. The array is strictly increasing, so for each new height you binary search for the first tail that is greater than or equal to it. If there is none, the height extends the longest chain, so append it; otherwise it replaces that tail, because a smaller tail is never worse for extending later. The final length of tails is the answer.

function maxEnvelopes(envelopes) {
  const sorted = [...envelopes].sort((a, b) => a[0] - b[0] || b[1] - a[1]); // width up, then height DOWN
  const tails = []; // tails[k] = smallest height that ends a chain of k + 1 envelopes

  for (const [, height] of sorted) {
    let lo = 0, hi = tails.length;
    while (lo < hi) { // first index whose tail is >= height
      const mid = (lo + hi) >> 1;
      if (tails[mid] < height) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = height; // extend the longest chain, or lower an existing tail
  }
  return tails.length;
}

Dry run: [[5, 4], [6, 4], [6, 7], [2, 3]]

Sorted by width ascending and height descending on ties: [2, 3], [5, 4], [6, 7], [6, 4]. Only the heights matter now: 3, 4, 7, 4.

The answer is 3: [2, 3], then [5, 4], then [6, 7]. The last 4 belongs to the second envelope of width 6, and it lands on the existing 4 rather than extending anything, so the two width-6 envelopes did not both enter a chain. Time is O(n log n) for the sort plus O(n log n) for the n binary searches, and the space is O(n). The tails array is not itself a valid chain, only a summary of the best tails.

The same table, filled on demand: a top-down template

Everything so far filled the table bottom-up, which means choosing a loop order that guarantees each cell's inputs are ready. The palindrome tables showed how that can go wrong. The other way is to write the recurrence the way you would state it, as a function, and cache what it returns. The function asks for the smaller subproblems it needs, and the cache makes sure each one is computed only once. The table gets filled in whatever order the recursion happens to need.

function lcsTopDown(a, b) {
  const memo = Array.from({ length: a.length }, () => new Array(b.length).fill(undefined));

  function solve(i, j) { // LCS of a.slice(i) and b.slice(j)
    if (i === a.length || j === b.length) return 0; // an empty suffix shares nothing
    if (memo[i][j] !== undefined) return memo[i][j]; // test for undefined: 0 is a real answer
    memo[i][j] = a[i] === b[j]
      ? 1 + solve(i + 1, j + 1)
      : Math.max(solve(i + 1, j), solve(i, j + 1));
    return memo[i][j];
  }
  return solve(0, 0);
}

Here the state is the suffix pair: solve(i, j) is the LCS of a.slice(i) and b.slice(j), so the recursion moves forward and the base case is running off the end. Prefixes work equally well; pick one and write down in a sentence what the state means before you code it. The template has four parts: the base cases, a cache check, the recurrence, and a cache write before returning.

The cost of either version is the number of states times the work per state: here (m × n) states at O(1) each. In an interview it is a sound plan to write the top-down version first when you cannot see the fill order yet, get it correct, and then offer to convert it to loops if the interviewer worries about the call stack.

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 so dp[i+1][j-1] comes first: by increasing length, or rows bottom-up, not rows top-down
• A grid with walls keeps the same recurrence with 0 on the walls; a cost per cell turns the sum into a minimum, with Infinity for neighbours that do not exist; four-direction moves mean a shortest-path problem, not this table
• "Return the actual subsequence, edits or items" → walk back from the answer cell asking which neighbour explains each value, and keep the full table to do it
• "Substring" or "subarray" (contiguous) against "subsequence" → the contiguous table resets to 0 on a mismatch, and its answer is the largest cell anywhere
• "How many ways" → add the options instead of taking a maximum, with a base case of 1 for the empty case; "is it possible" → OR them
• The largest square or rectangle that ends at a corner cell → look at the three neighbours that are already filled
• A pattern with wildcards or repeats against a string → a table over a prefix of each, and a star that means "match nothing" or "take one more"
• Pairs with two ordered properties and a large n → sort by one, run a longest-increasing-subsequence on the other, and sort ties the other way
• If you cannot see the fill order, write the recurrence as a memoized function first, and check the recursion depth against the constraints
• 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.