Matrix DP

Matrix (or Grid) DP problems involve finding a path or calculating a value on a 2D grid. The movement is usually restricted (e.g., only move Right or Down).

1. Unique Paths II (with Obstacles)

Problem Statement: You are a robot located at the top-left corner of an m x n grid. You can only move either down or right at any point in time. The grid contains obstacles marked as 1 and empty spaces marked as 0. How many unique paths are there to reach the bottom-right corner?

Recurrence Relation

Let dp[i][j] be the number of unique paths to reach cell (i, j).

  • Base Case: dp[0][0] = 1 (if no obstacle at start).
  • If grid[i][j] is an obstacle: dp[i][j] = 0.
  • Otherwise: dp[i][j] = dp[i-1][j] (from top) + dp[i][j-1] (from left).

Interactive Visualizer

Click on cells to toggle obstacles (dark blocks). Then click “Calculate Paths” to see how the number of paths propagates through the grid.

[!TIP] Try it yourself: Create a wall of obstacles and see how the path count drops to 0 behind it.

Click cells to toggle obstacles

Code Implementation: Unique Paths II

// Java
public class UniquePathsII {
  public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    int[][] dp = new int[m][n];

    // Base case
    if (obstacleGrid[0][0] == 0) {
      dp[0][0] = 1;
    }

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (obstacleGrid[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];
  }
}

// Go
func UniquePathsWithObstacles(obstacleGrid [][]int) int {
  m := len(obstacleGrid)
  n := len(obstacleGrid[0])
  dp := make([][]int, m)
  for i := range dp {
    dp[i] = make([]int, n)
  }

  if obstacleGrid[0][0] == 0 {
    dp[0][0] = 1
  }

  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if obstacleGrid[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]
}

2. Minimum Path Sum

Problem Statement: Given a grid filled with non-negative numbers, find a path from top-left to bottom-right which minimizes the sum of all numbers along its path. You can only move down or right.

Recurrence Relation

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

  • Boundary conditions:
  • Top row: Can only come from left.
  • Left column: Can only come from top.

Code Implementation: Minimum Path Sum

// Java
public class MinPathSum {
  public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (i == 0 && j == 0) continue; // Start

        int fromTop = (i > 0) ? grid[i - 1][j] : Integer.MAX_VALUE;
        int fromLeft = (j > 0) ? grid[i][j - 1] : Integer.MAX_VALUE;

        grid[i][j] += Math.min(fromTop, fromLeft);
      }
    }
    return grid[m - 1][n - 1];
  }
}

// Go
import "math"

func MinPathSum(grid [][]int) int {
  m := len(grid)
  n := len(grid[0])

  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if i == 0 && j == 0 {
        continue
      }

      fromTop := math.MaxInt32
      if i > 0 {
        fromTop = grid[i-1][j]
      }

      fromLeft := math.MaxInt32
      if j > 0 {
        fromLeft = grid[i][j-1]
      }

      if fromTop < fromLeft {
        grid[i][j] += fromTop
      } else {
        grid[i][j] += fromLeft
      }
    }
  }
  return grid[m-1][n-1]
}

3. Deep Dive Strategy Lab: Matrix DP

Intuition Through Analogy: The Delivery Drone

Think of Matrix DP like programming an autonomous delivery drone navigating a city grid from a warehouse (top-left) to a customer (bottom-right). The drone only has enough battery to move Right or Down to ensure it takes the shortest possible Manhattan distance.

  1. State Space (The Grid): Every intersection (i, j) is a subproblem. The drone’s optimal path to (i, j) depends only on the intersections immediately preceding it: (i-1, j) (coming from the North) and (i, j-1) (coming from the West).
  2. Obstacles (No-Fly Zones): In “Unique Paths II”, if an intersection is blocked by a tall building or no-fly zone, the number of valid paths reaching that specific point drops to 0. Any path that would have gone through it is effectively pruned.
  3. Weights (Toll Roads): In “Minimum Path Sum”, some intersections cost more battery (or time) due to wind resistance or tolls. To reach (i, j) optimally, the drone looks at the cost of arriving from the North vs. the West, picks the cheaper option, and adds the current intersection’s cost.

Complexity Analysis

Matrix DP problems usually have highly predictable complexities because we explicitly visit every cell in the m x n grid once.

Problem Time Complexity Space Complexity Space Optimization
Unique Paths II O(m * n) to visit every cell O(m * n) for DP table O(n) using a single 1D array (current row)
Min Path Sum O(m * n) to visit every cell O(1) if mutating input grid O(n) if input cannot be modified


[!TIP] Space Optimization Secret: Notice how the recurrence relation dp[i][j] = ... dp[i-1][j] ... dp[i][j-1] only relies on the current row i and the previous row i-1. You rarely need the full m x n matrix in memory. You can reduce space complexity to O(n) by only maintaining a 1D array of size n that updates in-place as you scan row by row.