2D dynamic programming

Overview

2D dynamic programming uses a state with two parameters, stored in a table dp[i][j]. The two dimensions usually mean positions in two sequences (compare strings), a position and a capacity (knapsack), a range [i, j] (interval DP), or a grid cell (paths).

The method is the same as 1D DP, but you must decide the fill order so that every cell's dependencies are computed first: row by row for sequence problems, by increasing length for interval problems. Many 2D tables can be compressed to one row because each row depends only on the previous one.

When to use it

• Two strings or arrays must be compared or aligned.
• A choice depends on a position and a remaining budget (capacity, k operations).
• The answer for a range [i, j] depends on smaller ranges (palindromes, burst balloons).
• Paths or costs over a grid.

Problem patterns it solves

Where it is used in real software

Key terms

dp[i][j]

Answer for the first i items of one input and the first j of another (or range i..j).

Fill order

The sequence of cells ensuring dependencies are ready.

Interval DP

States are ranges, filled by increasing length.

Row compression

Keep only the previous row (or one row updated carefully) to use O(n) space.

Edit distance, step by step

1. 1
   State

   dp[i][j] = minimum edits to convert word1[0..i) into word2[0..j).

2. 2
   Base cases

   dp[i][0] = i (delete everything); dp[0][j] = j (insert everything).

3. 3
   Characters match

   If word1[i - 1] === word2[j - 1], dp[i][j] = dp[i - 1][j - 1] (no edit needed).

4. 4
   Characters differ

   1 + min(dp[i - 1][j] delete, dp[i][j - 1] insert, dp[i - 1][j - 1] replace).

5. 5
   Answer

   dp[m][n].

Edit distance from "horse" to "ros"

Rows: prefixes of horse; columns: "", r, o, s

dp[5][3] = 3: replace h with r (rorse), delete r (rose), delete e (ros). Each cell looked only at its top, left, and top-left neighbors.

Implementation

1function minDistance(word1, word2) {2  const m = word1.length, n = word2.length;3  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));4  for (let i = 0; i <= m; i++) dp[i][0] = i;5  for (let j = 0; j <= n; j++) dp[0][j] = j;6  for (let i = 1; i <= m; i++) {7    for (let j = 1; j <= n; j++) {8      if (word1[i - 1] === word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];9      else dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);10    }11  }12  return dp[m][n];13}14 15// Interval DP: 516. Longest Palindromic Subsequence, filled by increasing length16function longestPalindromeSubseq(s) {17  const n = s.length;18  const dp = Array.from({ length: n }, () => new Array(n).fill(0));19  for (let i = n - 1; i >= 0; i--) {20    dp[i][i] = 1;21    for (let j = i + 1; j < n; j++) {22      dp[i][j] = s[i] === s[j] ? dp[i + 1][j - 1] + 2 : Math.max(dp[i + 1][j], dp[i][j - 1]);23    }24  }25  return dp[0][n - 1];26}27 28// 5. Longest Palindromic Substring by expanding around centers (O(n^2), O(1) space)29function longestPalindrome(s) {30  let start = 0, best = 0;31  const expand = (l, r) => {32    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }33    if (r - l - 1 > best) { best = r - l - 1; start = l + 1; }34  };35  for (let i = 0; i < s.length; i++) { expand(i, i); expand(i, i + 1); }36  return s.slice(start, start + best);37}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Wrong fill order in interval DP.

  Fix: Iterate i from n - 1 down to 0 (or by increasing length) so dp[i + 1][...] is ready.

• Overwriting values needed later in 1D compression.

  Fix: Save dp[j - 1] from the previous row in a temporary variable or use two rows.

• Confusing subsequence with substring.

  Fix: Subsequences skip characters (take max of neighbors); substrings must be contiguous (reset to 0 on mismatch).

Interview questions

Practice problems