2D Dynamic Programming: Tables, Grids, and String Comparisons

There's a point in DP learning where 1D arrays stop being enough. You're not just asking "what's the best at this index?" — you're asking "what's the best when considering the first i characters of one string and the first j characters of another?" That's when you need a 2D table.

Two-dimensional DP shows up in two distinct flavors: grid problems (navigating a 2D board) and string comparison problems (aligning or transforming two sequences). This article covers both with three problems: Unique Paths (the canonical grid DP), Longest Common Subsequence (the foundational string DP), and Edit Distance (the most complex of the three and a genuine favorite at Big Tech).

The Core Mental Model

In 1D DP, you fill a single row from left to right. In 2D DP, you fill a table — typically row by row, left to right. Each cell dp[i][j] represents the answer to a subproblem defined by two parameters: usually the first i elements of one input and the first j elements of another.

The relationship between cells is what changes between problems. Sometimes you only look left or up. Sometimes you look diagonally. The transitions tell you the structure.

Problem 1: Unique Paths (LeetCode 62)

The problem: An m × n grid. A robot starts at the top-left corner and must reach the bottom-right corner. It can only move right or down. How many unique paths are there?

Input: m = 3, n = 7
Output: 28

Why This Is DP

To reach cell (i, j), you either came from the left (i, j-1) or from above (i-1, j). The number of ways to reach (i, j) is the sum of both. No choice is made — it's pure counting.

State: dp[i][j] = number of distinct paths to reach cell (i, j) Base cases: the entire top row and left column are all 1 (only one way to traverse a straight line)

Approach 1: Naive Recursion

// O(2^(m+n)) time, O(m+n) space (call stack)
const uniquePaths = (m, n) => {
  const count = (row, col) => {
    if (row === m - 1 || col === n - 1) return 1; // Edge: only one direction possible
    return count(row + 1, col) + count(row, col + 1);
  };
  return count(0, 0);
};

Extremely wasteful — overlapping subproblems everywhere.

Approach 2: 2D DP Table

// O(m*n) time, O(m*n) space
const uniquePaths = (m, n) => {
  const dp = Array.from({ length: m }, () => new Array(n).fill(1));
 
  // First row and first column stay 1 (already set)
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
 
  return dp[m - 1][n - 1];
};

Approach 3: Space-Optimized DP

Each row only depends on the previous row, so you can compress to a 1D array:

// O(m*n) time, O(n) space
const uniquePaths = (m, n) => {
  let row = new Array(n).fill(1);
 
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      row[j] += row[j - 1]; // row[j] = prev_row[j] (from above) + row[j-1] (from left)
    }
  }
 
  return row[n - 1];
};

This is the version to go for in interviews once you've explained the 2D table version. It shows you understand which dimension is redundant.

Problem 2: Longest Common Subsequence (LeetCode 1143)

The problem: Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence can skip characters but must preserve order.

Input: text1 = "abcde", text2 = "ace"
Output: 3 — the LCS is "ace"

Building the Table

dp[i][j] = LCS of the first i characters of text1 and the first j characters of text2.

Two cases for each cell:

• If text1[i-1] === text2[j-1]: the characters match, so dp[i][j] = dp[i-1][j-1] + 1
• Otherwise: take the best from ignoring either character: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Base cases: dp[0][j] = 0 and dp[i][0] = 0 — empty string has no common subsequence.

The completed table for "abcde" vs "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

Approach 1: Recursion (Brute Force)

// O(2^(m+n)) time, O(m+n) space
const longestCommonSubsequence = (text1, text2) => {
  const lcs = (i, j) => {
    if (i === text1.length || j === text2.length) return 0;
    if (text1[i] === text2[j]) return 1 + lcs(i + 1, j + 1);
    return Math.max(lcs(i + 1, j), lcs(i, j + 1));
  };
  return lcs(0, 0);
};

Approach 2: Memoization (Top-Down DP)

// O(m*n) time, O(m*n) space
const longestCommonSubsequence = (text1, text2) => {
  const m = text1.length, n = text2.length;
  const memo = Array.from({ length: m }, () => new Array(n).fill(-1));
 
  const lcs = (i, j) => {
    if (i === m || j === n) return 0;
    if (memo[i][j] !== -1) return memo[i][j];
 
    if (text1[i] === text2[j]) {
      memo[i][j] = 1 + lcs(i + 1, j + 1);
    } else {
      memo[i][j] = Math.max(lcs(i + 1, j), lcs(i, j + 1));
    }
 
    return memo[i][j];
  };
 
  return lcs(0, 0);
};

Approach 3: Bottom-Up DP Table

// O(m*n) time, O(m*n) space
const longestCommonSubsequence = (text1, text2) => {
  const m = text1.length, n = text2.length;
  // (m+1) x (n+1) table, zero-initialized for base cases
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
 
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[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[m][n];
};

This is the canonical interview solution. Clear recurrence, O(m·n) time, and it's the foundation for Edit Distance.

Problem 3: Edit Distance (LeetCode 72)

The problem: Given two strings word1 and word2, return the minimum number of operations to convert word1 to word2. Allowed operations: insert a character, delete a character, replace a character.

Input: word1 = "horse", word2 = "ros"
Output: 3

This is genuinely hard, and it's a real question at FAANG. The complexity comes from having three operations to choose from at each step.

The State and Transitions

dp[i][j] = minimum edit distance between the first i characters of word1 and the first j characters of word2.

Three cases:

• Characters match (word1[i-1] === word2[j-1]): no operation needed, dp[i][j] = dp[i-1][j-1]
• Replace: change word1[i-1] to word2[j-1], costs 1 + dp[i-1][j-1]
• Delete from word1: costs 1 + dp[i-1][j]
• Insert into word1 (= delete from word2): costs 1 + dp[i][j-1]

When characters don't match: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

Base cases: converting to/from an empty string requires i or j operations respectively.

Approach 1: Recursion

// O(3^(m+n)) time without memoization, O(m+n) space
const minDistance = (word1, word2) => {
  const dist = (i, j) => {
    if (i === 0) return j; // Insert j characters
    if (j === 0) return i; // Delete i characters
 
    if (word1[i - 1] === word2[j - 1]) {
      return dist(i - 1, j - 1); // Characters match — no cost
    }
 
    return 1 + Math.min(
      dist(i - 1, j - 1), // Replace
      dist(i - 1, j),     // Delete
      dist(i, j - 1)      // Insert
    );
  };
 
  return dist(word1.length, word2.length);
};

Approach 2: Bottom-Up DP

// O(m*n) time, O(m*n) space
const minDistance = (word1, word2) => {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
  );
 
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // Free — characters already match
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j - 1], // Replace
          dp[i - 1][j],     // Delete word1[i-1]
          dp[i][j - 1]      // Insert (equiv: delete word2[j-1])
        );
      }
    }
  }
 
  return dp[m][n];
};

Approach 3: Space-Optimized

Since each row only depends on the previous row, you can drop to a two-row rolling array. That makes the space O(n) where n = word2.length — the row you allocate. If you also swap the arguments so the shorter string drives the row width, it becomes O(min(m, n)); the version below keeps the arguments as given.

// O(m*n) time, O(n) space
const minDistance = (word1, word2) => {
  const m = word1.length, n = word2.length;
  let prev = Array.from({ length: n + 1 }, (_, j) => j); // Base case: row 0
 
  for (let i = 1; i <= m; i++) {
    const curr = new Array(n + 1);
    curr[0] = i; // Base case: column 0
 
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        curr[j] = prev[j - 1];
      } else {
        curr[j] = 1 + Math.min(prev[j - 1], prev[j], curr[j - 1]);
      }
    }
 
    prev = curr;
  }
 
  return prev[n];
};

Interview Tips

On Unique Paths: Mention the obstacle grid variant (LeetCode 63) proactively — it's a natural follow-up and only requires one extra check: if grid[i][j] === 1, dp[i][j] = 0. The math solution with combinatorics breaks in that variant, which is why the DP approach is more general.

On LCS: LCS is a building block for several harder problems: Diff algorithms, DNA sequence alignment, and Shortest Common Supersequence (LeetCode 1092). The interviewer might ask you to reconstruct the actual subsequence — do that by backtracking through the DP table from dp[m][n] to dp[0][0], following the path that led to each cell's value.

On Edit Distance: The three-operation recurrence is the hardest part to internalize. A trick that helps: think of dp[i-1][j] as "I deleted from word1" (one fewer character in word1 to match), dp[i][j-1] as "I inserted into word1" (one fewer character in word2 left to cover), and dp[i-1][j-1] as "I replaced or matched." Once you have those semantics, the transitions feel natural rather than magic.

The broader lesson: 2D DP always traces back to "I have two parameters that define the subproblem." Grid problems use coordinates; string problems use prefix lengths. In both cases, filling the table from top-left to bottom-right and reading transitions from neighboring cells is the universal approach.