Overview

Opened with spaced rep Climb Stairs — clean implementation, no off-by-one. Unique Paths introduced with a combinatorial detour: James correctly identified the closed-form C(m+n-2, m-1) solution and understood why DP is still needed for the obstacle variant. Edit Distance: James derived the three-case recurrence and caught the OOB/base-case problem himself mid-implementation.

Concept

Unique Paths: dp[i][j] = number of paths from (0,0) to (i,j) moving only right or down. Base case: every cell in row 0 or column 0 has exactly 1 path. Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Closed form: C(m+n-2, m-1) — but DP generalizes to obstacles.

Edit Distance: dp[i][j] = minimum operations to transform word1[0..i-1] into word2[0..j-1]. Three operations from three neighbors:

• Delete word1[i]: dp[i-1][j] + 1
• Insert word2[j]: dp[i][j-1] + 1
• Replace/match: dp[i-1][j-1] + (0 if same, 1 if different)

Table is (m+1) × (n+1): row 0 = cost to build word2 prefix from empty string (= j inserts), col 0 = cost to reduce word1 prefix to empty string (= i deletes).

Implementation

Unique Paths II (with obstacles)

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

  // Rows indexed i top-to-bottom, columns indexed j left-to-right.
  // grid[i][j] === 1 means blocked; we overwrite open cells with path counts.
  grid[0][0] = 1
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) continue
      if (grid[i][j] === 1) {
        grid[i][j] = 0 // clear obstacle before neighbors read it
        continue
      }
      const above = i > 0 ? grid[i - 1][j] : 0
      const left = j > 0 ? grid[i][j - 1] : 0
      grid[i][j] = above + left
    }
  }
  return grid[m - 1][n - 1]
}

Key: clear obstacles to 0 before any neighbor reads them, so path counts (including 1) are never confused with obstacle markers.

Edit Distance (recurrence only — implementation deferred)

function editDistance(word1: string, word2: string): number {
  const m = word1.length,
    n = word2.length
  // dp is (m+1) × (n+1); dp[i][j] = min ops to turn word1[0..i-1] into word2[0..j-1]
  const dp: number[][] = 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++) {
      const sub = word1[i - 1] === word2[j - 1] ? 0 : 1
      dp[i][j] = Math.min(
        dp[i - 1][j] + 1, // delete from word1
        dp[i][j - 1] + 1, // insert into word1
        dp[i - 1][j - 1] + sub // replace or match
      )
    }
  }
  return dp[m][n]
}

Problems

Climb Stairs (spaced rep)

Clean O(1) space rolling-variable implementation. Correct recurrence and loop bounds. Minor: return n if n in {0,1,2} should return 1 for n=0 (one way to climb zero stairs: do nothing). Otherwise ✅.

Unique Paths

Robot in m × n grid, moves only right or down. How many paths to bottom-right?

Combinatorial insight: any path is exactly (m-1) downs and (n-1) rights in some order → C(m+n-2, m-1). DP equivalent to Pascal’s Triangle. DP generalizes to obstacles where closed form fails.

Base case intuition: row 0 and col 0 each have exactly 1 path — you can only move along the edge; any deviation requires a step you can’t take back.

Unique Paths II (with obstacles)

Same grid, grid[i][j] === 1 means blocked.

Approach: in-place DP, clear obstacles to 0 before computing, treat OOB as 0. See implementation above.

Sentinel trap: a cell with path count 1 is indistinguishable from an obstacle marker 1 — clear obstacles first, then fill path counts.

Edit Distance

Minimum insert/delete/replace operations to transform word1 into word2.

Recurrence: three-way min from above (delete), left (insert), diagonal (replace/match). Table is (m+1) × (n+1) with explicit base-case row (j inserts) and column (i deletes).

OOB lesson: defaulting OOB to 0 makes the minimum always 0; defaulting to Infinity doesn’t work because the correct OOB values are position-dependent. The solution is to not have OOB — seed the +1 row/column explicitly.