Dynamic Programming: 2D

When does 2D DP apply?

2D DP applies when the optimal subproblem state requires two independent variables — you cannot reduce the problem to a single index without losing information.

Four recurring patterns:

Decision tree:

Is the state defined by two independent bounded parameters?
  └─ Can dp[i][j] be computed from previously computed entries?
       └─ Yes → 2D DP.
            Define: state meaning, recurrence, base cases, iteration order.

Getting the state definition right before writing any code is the entire game.

Pattern 1: Grid DP

Unique Paths — LC 62

A robot starts at the top-left of an m × n grid and must reach the bottom-right. It can only move right or down. Count distinct paths.

State: dp[r][c] = number of paths from (0, 0) to (r, c). Recurrence: dp[r][c] = dp[r-1][c] + dp[r][c-1] — the robot arrived from above or from the left. Base case: First row and first column are all 1 (only one way to reach any cell in those rows/columns).

function uniquePaths(m: number, n: number): number {
  const dp = Array.from({ length: m }, () => new Array(n).fill(1))

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    }
  }

  return dp[m - 1][n - 1]
}

// Space-optimized: O(n) — only the current and previous row needed
function uniquePathsOptimized(m: number, n: number): number {
  let row = new Array(n).fill(1)
  for (let r = 1; r < m; r++) {
    const newRow = new Array(n).fill(1)
    for (let c = 1; c < n; c++) {
      newRow[c] = row[c] + newRow[c - 1]  // above + left
    }
    row = newRow
  }
  return row[n - 1]
}

Time: O(m × n). Space: O(n) optimized.

Minimum Path Sum — LC 64

Find the path from top-left to bottom-right (right/down only) that minimizes the sum of values along the path.

function minPathSum(grid: number[][]): number {
  const m = grid.length, n = grid[0].length
  const dp = grid.map(row => [...row])  // work on a copy

  for (let c = 1; c < n; c++) dp[0][c] += dp[0][c - 1]
  for (let r = 1; r < m; r++) dp[r][0] += dp[r - 1][0]

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] += Math.min(dp[r - 1][c], dp[r][c - 1])
    }
  }

  return dp[m - 1][n - 1]
}

Time: O(m × n). Space: O(1) if you’re allowed to modify the input in-place.

Unique Paths II — LC 63

Same as Unique Paths but cells marked 1 are obstacles. Set paths through any obstacle to 0.

function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  const m = obstacleGrid.length, n = obstacleGrid[0].length
  if (obstacleGrid[0][0] === 1 || obstacleGrid[m - 1][n - 1] === 1) return 0

  const dp = Array.from({ length: m }, () => new Array(n).fill(0))
  dp[0][0] = 1

  for (let r = 1; r < m; r++) dp[r][0] = obstacleGrid[r][0] === 1 ? 0 : dp[r - 1][0]
  for (let c = 1; c < n; c++) dp[0][c] = obstacleGrid[0][c] === 1 ? 0 : dp[0][c - 1]

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] = obstacleGrid[r][c] === 1 ? 0 : dp[r - 1][c] + dp[r][c - 1]
    }
  }

  return dp[m - 1][n - 1]
}

Pattern 2: String DP

Longest Common Subsequence — LC 1143

The foundational 2D string DP. Find the length of the longest subsequence common to both strings. Characters don’t have to be contiguous, but order must be preserved.

State: dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]. Recurrence:

• If characters match: dp[i][j] = dp[i-1][j-1] + 1
• If not: dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) — skip a character from one string

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length
  // Size (m+1) × (n+1). Row 0 and col 0 represent empty string — base case is 0.
  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]
}

// Reconstruct the actual LCS string by backtracking through the table
function reconstructLCS(text1: string, text2: string): string {
  const m = text1.length, n = text2.length
  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++) {
      dp[i][j] = text1[i - 1] === text2[j - 1]
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1])
    }
  }

  // Backtrack from dp[m][n]
  let i = m, j = n
  const result: string[] = []
  while (i > 0 && j > 0) {
    if (text1[i - 1] === text2[j - 1]) {
      result.push(text1[i - 1])
      i--; j--
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--
    } else {
      j--
    }
  }
  return result.reverse().join('')
}

Table walkthrough for "abcde" and "ace":

Answer: dp[5][3] = 3. Backtracking recovers "ace".

Edit Distance — LC 72

Minimum operations (insert, delete, replace) to convert word1 into word2.

State: dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1]. Base case: dp[i][0] = i (delete all i characters). dp[0][j] = j (insert all j characters). Recurrence:

• Characters match: dp[i][j] = dp[i-1][j-1] (no operation needed)
• Characters differ: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) — replace, delete, insert

function minDistance(word1: string, word2: string): number {
  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]
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j - 1],  // replace word1[i-1] with word2[j-1]
          dp[i - 1][j],      // delete word1[i-1]
          dp[i][j - 1]       // insert word2[j-1] into word1
        )
      }
    }
  }

  return dp[m][n]
}

Table walkthrough for "horse" → "ros":

Answer: 3 operations (replace ‘h’→‘r’, delete ‘r’, delete ‘e’).

Longest Common Substring (contrast with LCS)

Unlike LCS, a substring must be contiguous. Reset dp[i][j] to 0 on any mismatch — you cannot skip characters.

function longestCommonSubstring(s1: string, s2: string): number {
  const m = s1.length, n = s2.length
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))
  let maxLen = 0

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
        maxLen = Math.max(maxLen, dp[i][j])
      }
      // else: dp[i][j] remains 0 — contiguity is broken
    }
  }

  return maxLen
}

Key contrast: LCS skips mismatched characters (takes max of neighbors), Longest Common Substring resets to 0 on any mismatch.

Pattern 3: Knapsack

0/1 Knapsack

Given n items each with a weight and value, and a knapsack of capacity W, find the maximum value you can carry. Each item is either taken (1) or not (0) — you cannot take a fraction.

State: dp[i][w] = max value using the first i items with capacity w. Recurrence:

• Skip item i: dp[i][w] = dp[i-1][w]
• Take item i (if weights[i-1] <= w): dp[i][w] = dp[i-1][w - weights[i-1]] + values[i-1]

function knapsack(capacity: number, weights: number[], values: number[]): number {
  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]  // skip 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])
      }
    }
  }

  return dp[n][capacity]
}

// Space-optimized to O(W): iterate capacity right-to-left
function knapsackOptimized(capacity: number, weights: number[], values: number[]): number {
  const dp = new Array(capacity + 1).fill(0)

  for (let i = 0; i < weights.length; i++) {
    // Iterate right-to-left so dp[w - weights[i]] reflects the PREVIOUS item's row
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i])
    }
  }

  return dp[capacity]
}

Why right-to-left in the 1D version? If we iterated left-to-right, dp[w - weights[i]] might already include item i from the current iteration — counting the same item twice. Right-to-left reads from the “previous row” state.

Partition Equal Subset Sum — LC 416

Can you split the array into two subsets with equal sum? This reduces to: can you find a subset summing to total / 2?

function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0)
  if (total % 2 !== 0) return false
  const target = total / 2

  const dp = new Array(target + 1).fill(false)
  dp[0] = true

  for (const num of nums) {
    for (let w = target; w >= num; w--) {
      dp[w] = dp[w] || dp[w - num]
    }
  }

  return dp[target]
}

Time: O(n × target). Space: O(target). The boolean knapsack pattern: dp[w] = “can we form sum w?”

Target Sum — LC 494

Assign + or − to each number. Count the number of ways to reach the target sum.

Mathematical insight: Let P = sum of positive group, N = sum of negative group. Then P − N = target and P + N = total, so P = (total + target) / 2. Count subsets summing to P.

function findTargetSumWays(nums: number[], target: number): number {
  const total = nums.reduce((a, b) => a + b, 0)
  if ((total + target) % 2 !== 0 || Math.abs(target) > total) return 0
  const s = (total + target) / 2

  const dp = new Array(s + 1).fill(0)
  dp[0] = 1

  for (const num of nums) {
    for (let w = s; w >= num; w--) {
      dp[w] += dp[w - num]
    }
  }

  return dp[s]
}

Time: O(n × sum). Space: O(sum). Count DP: dp[w] = number of ways to form sum w.

Pattern 4: Interval DP

Interval DP solves problems over contiguous ranges [l, r]. The state dp[l][r] represents the answer for the subproblem on the subarray/substring from index l to r.

Critical iteration order: process shorter intervals before longer ones. Use a length outer loop from 2 to n, then an i inner loop. Never index into dp[i][j] before dp[i+1][j-1] or dp[i][j-1] is computed.

Burst Balloons — LC 312

Given n balloons with values nums, bursting balloon i earns nums[l] × nums[i] × nums[r] coins where l and r are its current neighbors. Maximize total coins.

The insight that makes this solvable: think about the last balloon burst in a range, not the first. If balloon k is the last to burst in range [l, r], then at the moment k is burst, all other balloons in (l, r) are already gone. So k’s neighbors are the boundary values outside the range — fixed and known.

State: dp[l][r] = max coins from bursting all balloons strictly between indices l and r, with sentinel value 1 added at both ends.

function maxCoins(nums: number[]): number {
  const balloons = [1, ...nums, 1]  // sentinels
  const n = balloons.length
  const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0))

  // Fill by increasing interval length
  for (let length = 2; length < n; length++) {
    for (let l = 0; l < n - length; l++) {
      const r = l + length
      // Try each k as the LAST balloon burst in the open interval (l, r)
      for (let k = l + 1; k < r; k++) {
        dp[l][r] = Math.max(
          dp[l][r],
          balloons[l] * balloons[k] * balloons[r] + dp[l][k] + dp[k][r]
        )
      }
    }
  }

  return dp[0][n - 1]
}

Time: O(n³). Space: O(n²).

Why “last burst” and not “first burst”? If you think of the first balloon burst in [l, r], you don’t know what its neighbors are when it’s burst — they depend on the order of future bursts, making the state non-Markovian. With “last burst”, the sentinel boundaries are exactly l and r — known at definition time.

Palindromic Substrings — LC 647

Count all palindromic substrings in s.

function countSubstrings(s: string): number {
  const n = s.length
  const dp: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false))
  let count = 0

  // Length 1: all single characters are palindromes
  for (let i = 0; i < n; i++) { dp[i][i] = true; count++ }

  // Length 2: equal adjacent pairs
  for (let i = 0; i < n - 1; i++) {
    if (s[i] === s[i + 1]) { dp[i][i + 1] = true; count++ }
  }

  // Length 3+: s[i..j] is a palindrome if s[i] === s[j] and s[i+1..j-1] is also
  for (let length = 3; length <= n; length++) {
    for (let i = 0; i <= n - length; i++) {
      const j = i + length - 1
      if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true
        count++
      }
    }
  }

  return count
}

Longest Palindromic Subsequence — LC 516

Find the length of the longest subsequence of s that forms a palindrome.

Recurrence:

• If s[i] === s[j]: dp[i][j] = dp[i+1][j-1] + 2 (both characters are part of the subsequence)
• Otherwise: dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (skip one endpoint)

function longestPalindromeSubseq(s: string): number {
  const n = s.length
  const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0))

  for (let i = 0; i < n; i++) dp[i][i] = 1  // base: single character

  for (let length = 2; length <= n; length++) {
    for (let i = 0; i <= n - length; i++) {
      const j = i + length - 1
      if (s[i] === s[j]) {
        dp[i][j] = (length === 2 ? 0 : dp[i + 1][j - 1]) + 2
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
      }
    }
  }

  return dp[0][n - 1]
}

Reading and reconstructing a 2D DP table

The value in dp[m][n] gives you the answer. To get the actual solution (not just its cost), backtrack through the table:

1. Start at the answer cell.
2. At each cell, determine which transition produced the stored value.
3. Move to the predecessor cell, recording the decision.

For LCS, at cell dp[i][j]:

• If text1[i-1] === text2[j-1] → the character was matched; move to dp[i-1][j-1].
• Else if dp[i-1][j] >= dp[i][j-1] → character from text1 was skipped; move up.
• Else → character from text2 was skipped; move left.

For Edit Distance, at each cell reverse-engineer whether a match, replace, delete, or insert produced the value.

Iteration order matters for interval DP. Shorter intervals must be fully computed before longer ones. The length outer loop guarantees dp[l][k] and dp[k][r] are both computed before dp[l][r].

Space optimization patterns

When optimization is safe: dp[i][j] depends only on the immediately preceding row (or same row, already computed). You can discard older rows.

When optimization is unsafe: You need the table for reconstruction, or the problem requires accessing non-adjacent previous rows.

Complexity summary