DP on Grids: Unique Paths and Minimum Path Sum

Grid DP solves problems where you move through a 2D matrix — usually from the top-left to the bottom-right, stepping only right or down — and you want to count paths or optimize a cost along the way. The state is simply the cell you’re at, and each cell’s answer combines the cells you could have come from. This page covers the two canonical problems: Unique Paths and Minimum Path Sum.

Unique Paths

How many distinct paths lead from the top-left to the bottom-right of an m × n grid, moving only right or down?

State: dp[i][j] = number of ways to reach cell (i, j).
Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1] (arrive from above or from the left).
Base cases: the entire first row and first column have exactly 1 path (you can only go straight).

int uniquePaths(int m, int n) {
    std::vector<std::vector<int>> dp(m, std::vector<int>(n, 1));
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    return dp[m - 1][n - 1];
}

int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int[] row : dp) Arrays.fill(row, 1);
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    return dp[m - 1][n - 1];
}

function uniquePaths(m, n) {
  const dp = Array.from({ length: m }, () => new Array(n).fill(1));
  for (let i = 1; i < m; i++)
    for (let j = 1; j < n; j++)
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  return dp[m - 1][n - 1];
}

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

Time O(mn), space O(mn). Since each cell uses only the row above and the cell to the left, one row suffices — O(n) space.

Minimum Path Sum

Each cell holds a cost. Find the path from top-left to bottom-right (right/down moves) that minimizes the sum of visited cells.

State: dp[i][j] = minimum cost to reach (i, j).
Transition: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
Base cases: dp[0][0] = grid[0][0]; the first row and column accumulate left-to-right / top-to-bottom (only one way in).

int minPathSum(std::vector<std::vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
    dp[0][0] = grid[0][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = grid[i][j] + std::min(dp[i - 1][j], dp[i][j - 1]);
    return dp[m - 1][n - 1];
}

int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    dp[0][0] = grid[0][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
    return dp[m - 1][n - 1];
}

function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  dp[0][0] = grid[0][0];
  for (let j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
  for (let i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
  for (let i = 1; i < m; i++)
    for (let j = 1; j < n; j++)
      dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
  return dp[m - 1][n - 1];
}

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    return dp[m - 1][n - 1]

For beginners: Grid DP is just Climbing Stairs in two dimensions. Each cell’s answer is built from the (one or two) cells you could step from. Fill the first row and column first — they’re the base cases — then sweep the interior.

Handling obstacles

A common variant blocks some cells (e.g. a 1 in the grid means a wall). Set dp to 0 at any obstacle, and stop the first-row/column propagation once it hits one — there’s no path through a wall.

int uniquePathsWithObstacles(std::vector<std::vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    if (grid[0][0] == 1) return 0;
    std::vector<std::vector<long long>> dp(m, std::vector<long long>(n, 0));
    dp[0][0] = 1;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) { dp[i][j] = 0; continue; }
            if (i > 0) dp[i][j] += dp[i - 1][j];
            if (j > 0) dp[i][j] += dp[i][j - 1];
        }
    return (int)dp[m - 1][n - 1];
}

int uniquePathsWithObstacles(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    if (grid[0][0] == 1) return 0;
    long[][] dp = new long[m][n];
    dp[0][0] = 1;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) { dp[i][j] = 0; continue; }
            if (i > 0) dp[i][j] += dp[i - 1][j];
            if (j > 0) dp[i][j] += dp[i][j - 1];
        }
    return (int) dp[m - 1][n - 1];
}

function uniquePathsWithObstacles(grid) {
  const m = grid.length, n = grid[0].length;
  if (grid[0][0] === 1) return 0;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  dp[0][0] = 1;
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) { dp[i][j] = 0; continue; }
      if (i > 0) dp[i][j] += dp[i - 1][j];
      if (j > 0) dp[i][j] += dp[i][j - 1];
    }
  return dp[m - 1][n - 1];
}

def unique_paths_with_obstacles(grid):
    m, n = len(grid), len(grid[0])
    if grid[0][0] == 1:
        return 0
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[i][j] = 0
                continue
            if i > 0:
                dp[i][j] += dp[i - 1][j]
            if j > 0:
                dp[i][j] += dp[i][j - 1]
    return dp[m - 1][n - 1]

Pitfall: Don’t forget to check the start and end cells for obstacles. If grid[0][0] is blocked the answer is 0, and naively setting dp[0][0] = 1 would give a wrong count.

Complexity

Problem	Time	Space (optimized)
Unique paths	O(mn)	O(n)
Minimum path sum	O(mn)	O(n)

Going deeper: Unique Paths also has a pure combinatorics answer — C(m+n-2, m-1) — because every path is a fixed arrangement of right/down moves. The DP generalizes to obstacles and weighted costs where the formula doesn’t apply.

Next, consolidate everything in DP on Subsequences & Strings, then test yourself with the DP exercises.