DP on Grids
Counting paths through a grid, or the cheapest way across it, is dynamic programming you can see.
The problem
A delivery robot sits in the top-left cell of an m × n warehouse grid and must reach the
bottom-right dock. It can only roll right or down. How many distinct routes are there?
And if each cell has a crossing cost — congestion, a ramp, a puddle — what is the cheapest
route across?
Unlike string DP, you do not have to imagine the table: the grid is the table. That makes grid DP the most visual member of the family, and a perfect place to build intuition you will reuse everywhere else.
A first attempt
Recurse from the start. From a cell, the number of paths to the goal is paths-going-right plus paths-going-down.
def paths(r, c, m, n):
if r == m - 1 and c == n - 1:
return 1
if r >= m or c >= n:
return 0
return paths(r + 1, c, m, n) + paths(r, c + 1, m, n)Each call spawns two more, so this is roughly O(2^(m+n)). And it is wasteful in an obvious
way: the cell at (2, 2) is reached by many different prefixes, and each one recomputes
everything below it from scratch.
The insight
A cell's answer depends only on its neighbors, and neighbors form a grid, not a tree:
dp[r][c]depends on the cell above(r-1, c)and the cell to the left(r, c-1). Fill the grid top-left to bottom-right and every cell you need is already done.
+---+---+---+
| 1 | 1 | 1 | paths grid:
+---+---+---+ each cell = above + left
| 1 | 2 | 3 |
+---+---+---+
| 1 | 3 | 6 | bottom-right = answer
+---+---+---+For counting paths you add the two neighbors. For the cheapest crossing you take the min of the two neighbors and add the current cell's cost. Same geometry, different combine operator — exactly the pattern from earlier lessons.
How it works
Take Minimum Path Sum: a grid of costs, move right or down, minimize the total.
Define the state
dp[r][c] = the minimum cost to reach cell (r, c) from the start, including both endpoints.
The answer is dp[m-1][n-1].
Seed the edges
The first cell is just its own cost. The top row can only be reached from the left, and the left column only from above, so each is a running prefix sum along that edge.
The recurrence
For an interior cell you arrived from above or from the left; pick the cheaper:
dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]).
Sweep in reading order
Go row by row, left to right. Both dp[r-1][c] and dp[r][c-1] are already filled, so one
pass completes the grid.
The code
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [row[:] for row in grid]
for r in range(m):
for c in range(n):
if r == 0 and c == 0:
continue
up = dp[r - 1][c] if r > 0 else float('inf')
left = dp[r][c - 1] if c > 0 else float('inf')
dp[r][c] = grid[r][c] + min(up, left)
return dp[m - 1][n - 1]function minPathSum(grid: number[][]): number {
const m = grid.length, n = grid[0].length;
const dp = grid.map((row) => row.slice());
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (r === 0 && c === 0) continue;
const up = r > 0 ? dp[r - 1][c] : Infinity;
const left = c > 0 ? dp[r][c - 1] : Infinity;
dp[r][c] = grid[r][c] + Math.min(up, left);
}
}
return dp[m - 1][n - 1];
}class Solution {
int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (r == 0 && c == 0) { dp[r][c] = grid[r][c]; continue; }
int up = r > 0 ? dp[r - 1][c] : Integer.MAX_VALUE;
int left = c > 0 ? dp[r][c - 1] : Integer.MAX_VALUE;
dp[r][c] = grid[r][c] + Math.min(up, left);
}
}
return dp[m - 1][n - 1];
}
}#include <limits.h>
int min_path_sum(int **grid, int m, int n) {
int dp[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (r == 0 && c == 0) { dp[r][c] = grid[r][c]; continue; }
int up = r > 0 ? dp[r - 1][c] : INT_MAX;
int left = c > 0 ? dp[r][c - 1] : INT_MAX;
dp[r][c] = grid[r][c] + (up < left ? up : left);
}
}
return dp[m - 1][n - 1];
}int minPathSum(vector<vector<int>> &grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp = grid;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (r == 0 && c == 0) continue;
int up = r > 0 ? dp[r - 1][c] : INT_MAX;
int left = c > 0 ? dp[r][c - 1] : INT_MAX;
dp[r][c] = grid[r][c] + min(up, left);
}
}
return dp[m - 1][n - 1];
}Complexity
| Approach | Time | Space |
|---|---|---|
| Naive recursion | O(2^(m+n)) | O(m + n) stack |
| Grid DP | O(m × n) | O(m × n) |
| Single-row DP | O(m × n) | O(n) |
Every cell is computed once with O(1) work, so time is simply the number of cells. Since each
row uses only the row above and the value to its left, one rolling row of length n suffices
for O(n) space.
When to use it
The grid is the table
Grid DP is the clearest picture of dynamic programming: fill cells in dependency order, combining a couple of neighbors. Obstacles are handled by setting blocked cells to 0 paths or infinite cost. When movement is only right/down (a DAG), plain DP works; add up/left moves and you need Dijkstra or BFS instead, because cells can depend on each other cyclically.
Practice
Recap
- Grid DP makes the table literal: each cell combines the cell above and the cell to the left.
- Add neighbors to count paths; take the min/max plus the cell's cost to optimize a crossing.
- It works only when moves point one way (a DAG); collapse to a single row for O(n) space.
How is this guide?
Last updated on