Grid DP (unique paths / min path sum)
Why it exists
Problem: Navigating a grid recursively by branching right and down from every cell duplicates work, as many paths converge on the same intermediate cells, leading to exponential time bounds.
Better idea: A grid inherently provides overlapping subproblems. By building up the solution cell-by-cell from the top-left, we can store the result for each cell and reuse it to compute its neighbors in O(1) time.
Mental model
To reach a cell, you must have stepped from either the cell directly above it or the cell directly to its left. Combine those two past answers to get the current answer.
We traverse a 2D matrix row by row. Because paths can only move right or down, the optimal state of any cell depends strictly on the top and left neighbors. For counting paths, we sum them. For finding a minimal cost, we take the minimum of the two and add the current cell's cost.
Repeated decision: for this cell, do I arrive by moving right (from the cell to my left) or down (from the cell above) -- and for min-path-sum, which of those two gives the cheaper total?
Explanation
Grid DP problems are the most literal visualization of dynamic programming, because the DP table perfectly overlays the problem's 2D grid. Both Unique Paths and Min Path Sum use the exact same structural shape.
For **Unique Paths**, we count the number of ways to reach the bottom-right from the top-left, moving only right and down.
State: `dp[r][c]` is the number of unique paths to row `r`, column `c`.
Recurrence: `dp[r][c] = dp[r-1][c] + dp[r][c-1]`.
Base cases: `dp[0][*] = 1` and `dp[*][0] = 1`. There is only one way to move strictly along the top edge or left edge.
For **Min Path Sum**, each cell has a cost, and we want the cheapest path to the bottom-right.
State: `dp[r][c]` is the minimum cost to reach row `r`, column `c`.
Recurrence: `dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])`.
Base cases: Cells on the top row accumulate costs horizontally from the left. Cells on the left column accumulate costs vertically from above.
Both variants take `O(rows * cols)` time and space. However, notice that computing any row only strictly requires the values from the immediately preceding row. This allows us to space-optimize the `O(rows * cols)` table down to a single 1D rolling array of size `O(cols)`, a textbook application of 2D-to-1D space optimization.
Let's trace a `3x3` grid for both variants to see how only the combining operation changes.
**Unique Paths (Counting ways):**
- Row 0 (top edge): `[1, 1, 1]` (only 1 way to move strictly right).
- Row 1: `[1, dp[0][1]+dp[1][0] = 2, dp[0][2]+dp[1][1] = 3]`.
- Row 2: `[1, dp[1][1]+dp[2][0] = 3, dp[1][2]+dp[2][1] = 6]`.
The bottom-right cell is 6, so there are 6 unique paths.
**Min Path Sum (Finding cheapest path):**
Given costs: `Row 0 [1, 3, 1]`, `Row 1 [1, 5, 1]`, `Row 2 [4, 2, 1]`.
- Row 0: Accumulate left-to-right. `[1, 1+3=4, 4+1=5]`.
- Row 1:
- Col 0: Accumulate top-down. `1 + 1 = 2`.
- Col 1: `cost(5) + min(up:4, left:2) = 5 + 2 = 7`.
- Col 2: `cost(1) + min(up:5, left:7) = 1 + 5 = 6`.
- Row result: `[2, 7, 6]`.
- Row 2:
- Col 0: Accumulate top-down. `2 + 4 = 6`.
- Col 1: `cost(2) + min(up:7, left:6) = 2 + 6 = 8`.
- Col 2: `cost(1) + min(up:6, left:8) = 1 + 6 = 7`.
The bottom-right cell is 7, the minimum cost to traverse the grid.
Key points
- DAG Structure: These problems only work with DP because moves are strictly one-directional (right/down). This prevents cycles and makes the grid a Directed Acyclic Graph (DAG).
- Shared Recurrence Shape: Both algorithms rely on inspecting the top and left neighbors. Summing them counts paths, while taking the minimum finds the cheapest route.
- Space Optimization: Because row `r` only looks at row `r-1`, a 2D grid DP can almost always be optimized to use `O(cols)` space.
Common mistakes
- Out-of-bounds neighbor reads: Forgetting to handle the first row and first column correctly causes out-of-bounds exceptions when trying to read the non-existent top or left neighbors.
- Allowing up or left moves: If a grid allows moving in all 4 directions, it is no longer a DP problem because cyclic dependencies exist. You must use a graph search (like BFS or Dijkstra) instead.
Recall questions
- What is the recurrence relation for the Unique Paths problem?
- Why can the space complexity of Grid DP be optimized from 2D to 1D?
- Why would adding 'up' and 'left' moves break the DP approach?
Questions & answers
Count unique paths from top-left to bottom-right on a grid that contains obstacles (where paths cannot pass).
If `grid[r][c]` is an obstacle, set `dp[r][c] = 0`. Otherwise, use the standard Unique Paths recurrence.
Approach: An obstacle simply means 0 valid paths pass through that specific cell.
Find the maximum path sum in a triangle of numbers, starting from the top and moving to adjacent numbers on the row below.
Process the triangle from the bottom row up to the top. `dp[r][c] = triangle[r][c] + max(dp[r+1][c], dp[r+1][c+1])`.
Approach: It's the same Grid DP shape applied to a jagged array, computed bottom-up for simplicity.
Continue learning
Previous: Space optimization