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 (red 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

Think of this chapter like budget planning across months. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?