Matrix DP & BFS

Min Path Sum

Find the path from top-left to bottom-right with minimum sum (moving only right or down). dp[i][j] = grid[i][j] + min(dp[i−1][j], dp[i][j−1]). Fill row by row. Can optimize to O(n) space.

O(m*n)

How It Works

Minimum path sum asks for the cheapest route from the top-left to the bottom-right cell moving only right or down. Because every path into cell (i, j) must arrive from the cell above or the cell to the left, the best cost to reach (i, j) is grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Filling the table row by row guarantees both dependencies are ready when needed.

The recursion without memoization explores an exponential number of paths — roughly C(m+n, m) of them — while the DP computes each cell's answer exactly once, giving O(m*n) time. Since each row depends only on the previous row, the table compresses to a single rolling array of length n for O(n) space, or the grid itself can be overwritten for O(1) extra space. First-row and first-column cells have a single predecessor and form the base cases.

Step-by-Step Visualization

Min path sum in 3x3 grid

Start(0,0)=1

1/3

Code

Java

static int minPathSum(int[][] grid) {
  int m = grid.length, n = grid[0].length;

  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++) {
      if (i == 0 && j == 0) continue;
      else if (i == 0) grid[i][j] += grid[i][j-1];
      else if (j == 0) grid[i][j] += grid[i-1][j];
      else grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
    }
  return grid[m-1][n-1];
}

Tips & Gotchas

1dp[i][j] = min path sum to reach (i,j)

2Can come from top or left: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

3First row and column: only one way to reach them

Practice Problems

1Minimum Path Sum
2Unique Paths
3Unique Paths II
4Triangle

About the Matrix DP & BFS Pattern

Many grid problems are graph problems in disguise. Each cell is a node, adjacent cells are edges. Use BFS for shortest paths, DFS for connectivity, or DP for optimal paths.

Key insight

For traversal: use direction arrays dx=[0,0,1,-1], dy=[1,-1,0,0]. For sorted matrix search, start from top-right corner. For grid DP, fill row by row — current cell depends on top and left.

Common Matrix Interview Problems

Spiral Matrix
Rotate Image
Search a 2D Matrix
Number of Islands
Maximal Square
Set Matrix Zeroes
Word Search

Frequently Asked Questions

Why does this DP fail if moves in all four directions are allowed?

The right-and-down restriction makes the grid a DAG, so cells can be evaluated in a fixed topological order. With four-directional movement, paths can loop back, the subproblem dependencies become cyclic, and the problem turns into a shortest-path question best solved with Dijkstra or 0-1 BFS instead.

How does Unique Paths relate to Minimum Path Sum?

They share the same dependency structure but a different combine step: Unique Paths adds the counts from the top and left neighbors instead of taking a min plus the cell cost. Recognizing that a grid problem decomposes over the top and left neighbors is the transferable insight.