All Roadmaps›🧠 Data Structures & Algorithms›Phase 3›DP — 2D Problems (Grid, LCS, Edit Distance)

DP — 2D Problems (Grid, LCS, Edit Distance)

0/12 in this phase0/57 across the roadmap

📖 Concept

2D DP problems use a table dp[i][j] where each cell depends on adjacent cells. Common in grid paths, string comparison, and interval problems.

Common 2D DP patterns:

1. Grid paths:

  • dp[i][j] = number of ways / min cost to reach cell (i,j)
  • Depends on: dp[i-1][j] (from above) and dp[i][j-1] (from left)

2. Two-string problems (LCS, Edit Distance):

  • dp[i][j] = answer for first i chars of s1 and first j chars of s2
  • Depends on: dp[i-1][j], dp[i][j-1], dp[i-1][j-1]

3. Interval problems:

  • dp[i][j] = answer for range [i, j]
  • Depends on: dp[i][k] and dp[k+1][j] for all k in [i, j)

Top 2D DP problems:

  1. Unique Paths — ways to traverse grid from top-left to bottom-right
  2. Minimum Path Sum — min cost path in grid
  3. LCS — longest common subsequence of two strings
  4. Edit Distance — min operations to transform one string to another
  5. 0/1 Knapsack — max value with weight constraint

🏠 Real-world analogy: 2D DP is like filling out a spreadsheet where each cell's formula references cells above and to the left. You fill row by row, and each cell builds on previously computed values.

💻 Code Example

codeTap to expand ⛶
1// UNIQUE PATHS — Grid traversal
2function uniquePaths(m: number, n: number): number {
3  const dp = Array.from({length: m}, () => new Array(n).fill(1));
4  for (let i = 1; i < m; i++) {
5    for (let j = 1; j < n; j++) {
6      dp[i][j] = dp[i-1][j] + dp[i][j-1];
7    }
8  }
9  return dp[m-1][n-1];
10}
11

12// MINIMUM PATH SUM
13function minPathSum(grid: number[][]): number {
14  const m = grid.length, n = grid[0].length;
15  const dp = Array.from({length: m}, () => new Array(n).fill(0));
16  dp[0][0] = grid[0][0];
17  for (let i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
18  for (let j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
19  for (let i = 1; i < m; i++) {
20    for (let j = 1; j < n; j++) {
21      dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
22    }
23  }
24  return dp[m-1][n-1];
25}
26

27// LONGEST COMMON SUBSEQUENCE (LCS)
28function longestCommonSubsequence(s1: string, s2: string): number {
29  const m = s1.length, n = s2.length;
30  const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
31  for (let i = 1; i <= m; i++) {
32    for (let j = 1; j <= n; j++) {
33      if (s1[i-1] === s2[j-1]) {
34        dp[i][j] = dp[i-1][j-1] + 1;
35      } else {
36        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
37      }
38    }
39  }
40  return dp[m][n];
41}
42

43// EDIT DISTANCE (Levenshtein)
44function editDistance(s1: string, s2: string): number {
45  const m = s1.length, n = s2.length;
46  const dp = Array.from({length: m+1}, (_, i) =>
47    Array.from({length: n+1}, (_, j) => i === 0 ? j : j === 0 ? i : 0)
48  );
49  for (let i = 1; i <= m; i++) {
50    for (let j = 1; j <= n; j++) {
51      if (s1[i-1] === s2[j-1]) {
52        dp[i][j] = dp[i-1][j-1]; // No operation needed
53      } else {
54        dp[i][j] = 1 + Math.min(
55          dp[i-1][j],    // Delete
56          dp[i][j-1],    // Insert
57          dp[i-1][j-1]   // Replace
58        );
59      }
60    }
61  }
62  return dp[m][n];
63}
64

65// 0/1 KNAPSACK
66function knapsack(weights: number[], values: number[], capacity: number): number {
67  const n = weights.length;
68  const dp = Array.from({length: n+1}, () => new Array(capacity+1).fill(0));
69  for (let i = 1; i <= n; i++) {
70    for (let w = 1; w <= capacity; w++) {
71      if (weights[i-1] <= w) {
72        dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1]);
73      } else {
74        dp[i][w] = dp[i-1][w];
75      }
76    }
77  }
78  return dp[n][capacity];
79}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Unique paths in a grid (with and without obstacles)
  2. Minimum path sum in a grid
  3. Longest common subsequence
  4. Edit distance (Levenshtein distance)
  5. 0/1 Knapsack problem
  6. Longest palindromic subsequence
  7. Regular expression matching
  8. Interleaving string
  9. Distinct subsequences (count ways s has subsequence t)
  10. Maximal square of 1s in a binary matrix

⚠️ Common Mistakes

  • Off-by-one when initializing 2D DP for string problems — dp is (m+1)×(n+1), strings are 0-indexed

  • Not initializing the first row and column for grid DP — they represent base cases

  • Confusing subsequence (not contiguous) with substring (contiguous) — LCS is subsequence

  • Not understanding edit distance operations — insert, delete, replace correspond to specific dp directions

  • Using 2D space when 1D suffices — many 2D problems can be optimized to use only the previous row

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for DP — 2D Problems (Grid, LCS, Edit Distance)

← PreviousDP — 1D Problems (Fibonacci, Climbing Stairs, House Robber)Next →DP — Advanced (Knapsack, Interval, State Machines)