Dynamic Programming

2D Dynamic Programming

Written by Swapnil RajaUpdated 29 Aug 2026

You need a second dimension when the answer depends on two independent positions - how far through each of two strings, or a row and a column in a grid.

Unique paths - the simplest 2D table

Counting routes through a grid

javascript

function uniquePaths(rows, cols) {
  const table = Array.from({ length: rows }, () => new Array(cols).fill(1))

  for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      // Arrive from above or from the left.
      table[r][c] = table[r - 1][c] + table[r][c - 1]
    }
  }

  return table[rows - 1][cols - 1]
}

console.log(uniquePaths(3, 7))  // 28

The first row and column are all 1 - there is exactly one way to reach any of them. That is why the table is initialised to 1 and the loops start at index 1.

Minimum path sum - the same table, different rule

Cheapest route

javascript

function minPathSum(grid) {
  const rows = grid.length
  const cols = grid[0].length
  const table = Array.from({ length: rows }, () => new Array(cols).fill(0))

  table[0][0] = grid[0][0]

  for (let c = 1; c < cols; c++) table[0][c] = table[0][c - 1] + grid[0][c]
  for (let r = 1; r < rows; r++) table[r][0] = table[r - 1][0] + grid[r][0]

  for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      table[r][c] = grid[r][c] + Math.min(table[r - 1][c], table[r][c - 1])
    }
  }

  return table[rows - 1][cols - 1]
}

console.log(minPathSum([[1,3,1], [1,5,1], [4,2,1]]))  // 7

Edit distance - the classic two-string problem

Levenshtein distance

javascript

function editDistance(a, b) {
  const table = Array.from({ length: a.length + 1 }, () =>
    new Array(b.length + 1).fill(0)
  )

  // Turning a prefix into the empty string costs one delete per character.
  for (let i = 0; i <= a.length; i++) table[i][0] = i
  for (let j = 0; j <= b.length; j++) table[0][j] = j

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        table[i][j] = table[i - 1][j - 1]   // free
      } else {
        table[i][j] = 1 + Math.min(
          table[i - 1][j],      // delete
          table[i][j - 1],      // insert
          table[i - 1][j - 1]   // replace
        )
      }
    }
  }

  return table[a.length][b.length]
}

console.log(editDistance("kitten", "sitting"))  // 3

The three options in that Math.min are the three edits, and the initialised first row and column are the base cases. This is the algorithm behind spell check and diff.

Reducing to one row

When each row depends only on the row above, the full table is unnecessary:

O(n) space instead of O(n × m)

javascript

function uniquePathsSmall(rows, cols) {
  let row = new Array(cols).fill(1)

  for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      // row[c] still holds the value from the row above.
      row[c] = row[c] + row[c - 1]
    }
  }

  return row[cols - 1]
}

console.log(uniquePathsSmall(3, 3))  // 6

Do this last. Build the full table, confirm it is correct, then collapse it - debugging a collapsed table is considerably harder.

1D or 2D?

One sequence, answer depends on earlier positions - 1D.
Two sequences compared - 2D, one dimension each.
A grid - 2D, naturally.
One sequence plus a budget or capacity - 2D, though often reducible to 1D.

Reading the grid

In a 2D table, dp[i][j] almost always means "the answer using the first i of one input and the first j of the other". Once you fix that meaning, the recurrence follows from asking what the last decision could have been.

Edit distance

javascript

function editDistance(a, b) {
  const rows = a.length
  const cols = b.length
  const dp = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0))

  // Turning a prefix into the empty string costs one delete per character.
  for (let i = 0; i <= rows; i++) dp[i][0] = i
  for (let j = 0; j <= cols; j++) dp[0][j] = j

  for (let i = 1; i <= rows; i++) {
    for (let j = 1; j <= cols; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]           // characters match: free
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],      // delete from a
          dp[i][j - 1],      // insert into a
          dp[i - 1][j - 1]   // substitute
        )
      }
    }
  }

  return dp[rows][cols]
}

console.log(editDistance("kitten", "sitting"))  // 3

The three neighbours map exactly onto the three edits. Any 2D DP is easier to debug if you can say, for each direction you read from, which decision it represents.

Collapsing a row

When row i depends only on row i - 1, you can keep two rows instead of the whole grid and drop space from O(n·m) to O(m). Do this after the full version works - the index handling gets fiddly, and a correct O(n·m) answer beats a broken optimised one.

Previous1D Dynamic Programming NextBitmask Dynamic Programming