2-D Dynamic Programming

Grid-based DP problems like unique paths and minimum path sum use a 2-D table, but each row depends only on the one above, so a single rolling row collapses space from O(mn) to O(n).

5 min read Level 4/5 #dsa#dp#2d-dp

What you'll learn

Build and fill a 2-D dp table for unique paths and minimum path sum
Identify when only the previous row is needed and apply row-rolling
State the time and space complexity before and after the optimization

Two-dimensional DP problems use a state that depends on two indices — typically (row, col) for grid problems. The full table uses O(m * n) space, but many grids only look at the cell directly above and the cell to the left, so you can keep just one row and update it in place.

Unique Paths

Problem: Count paths from top-left to bottom-right of an m×n grid, moving only right or down.

State: dp[r][c] = number of paths to reach (r, c). Recurrence: dp[r][c] = dp[r-1][c] + dp[r][c-1] Base cases: First row and first column are all 1 (only one direction to travel).

Full table version — O(mn) time, O(mn) space:

function uniquePaths(m, n) {
  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];
}

Row-rolling version — O(mn) time, O(n) space. A single row is reused; dp[c] holds the value for the current row while the old dp[c] still holds the previous row’s value until overwritten:

function uniquePathsOpt(m, n) {
  const dp = new Array(n).fill(1);   // represents first row
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[c] += dp[c - 1];            // dp[c] was above; dp[c-1] is left
    }
  }
  return dp[n - 1];
}

console.log(uniquePathsOpt(3, 7)); // 28

Minimum Path Sum

Problem: Given a grid of non-negative integers, find the path from top-left to bottom-right (right/down moves only) with the minimum sum.

State: dp[r][c] = minimum sum to reach (r, c). Recurrence: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]) Base cases: dp[0][0] = grid[0][0]; first row and column accumulate prefix sums.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const dp = new Array(n).fill(0);

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (r === 0 && c === 0) {
        dp[c] = grid[0][0];
      } else if (r === 0) {
        dp[c] = dp[c - 1] + grid[r][c];   // only left neighbor
      } else if (c === 0) {
        dp[c] = dp[c] + grid[r][c];       // only above neighbor
      } else {
        dp[c] = Math.min(dp[c], dp[c - 1]) + grid[r][c];
      }
    }
  }
  return dp[n - 1];
}

const grid = [[1,3,1],[1,5,1],[4,2,1]];
console.log(minPathSum(grid)); // 7  (1→3→1→1→1)

Time and Space Summary

Version	Time	Space
Full 2-D table	O(m * n)	O(m * n)
Row-rolling	O(m * n)	O(n)

The row-rolling trick applies whenever dp[r][c] depends only on the current row and the immediately previous row. If you need to reconstruct the actual path, keep the full table or a separate parent array.

Up Next

The knapsack problem introduces a weight dimension and a choice dimension, making it the canonical 2-D DP with a weight-indexed rolling array.

0/1 Knapsack →