2D Dynamic Programming

Written by Swapnil RajaPublished 28 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

Previous1D Dynamic Programming NextGreedy Algorithms Explained

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

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

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]
}

2D Dynamic Programming

Unique paths - the simplest 2D table

Minimum path sum - the same table, different rule

Edit distance - the classic two-string problem

Reducing to one row

1D or 2D?