DP on Grids

Robots on a warehouse floor, a character crossing a game map, a cheapest route through a cost matrix: when you may only move right or down, every cell’s answer comes from just two neighbours.

intermediate⏱ 10 min read

←Builds on

101-D DP: Coins & LISGrid DP is 1-D DP with a second index: each cell reads the one above and the one to the left.

Leads to→

100-1 KnapsackThe knapsack table is a grid: items down the side, capacities across the top.10Longest Common SubsequenceThe LCS table is a grid over prefixes of the two strings, filled cell by cell.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Counting paths: add the two cells you came from

How many ways can you walk from the top left to the bottom right corner of a grid, moving only right or down?

Every path into cell (i, j) arrives either from above or from the left, and those two groups do not overlap. So

ways[i][j] = ways[i−1][j] + ways[i][j−1]

The top row and left column have exactly one way each (a straight line), which gives the base cases. Fill row by row, left to right, and both neighbours are always ready.

On a 4 × 5 grid the corner gets 35. You may recognise Pascal’s triangle: the answer is the binomial coefficient C(m+n−2, m−1). But the DP is what survives when the problem changes, for example when some cells are blocked.

02Cheapest path: min instead of plus

Now each cell has a cost, and you want the path with the smallest total. Same two neighbours, different combine:

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

with dp[0][0] = grid[0][0], and the first row and column as running sums (only one way in).

On the grid in the figure the corner gets 44. To print the route, start at the corner and repeatedly step to whichever of top or left has the smaller dp, until you reach the start. That is the same walk back you did for coins.

Why no BFS or Dijkstra? Because moves only go right or down, the dependency graph is a DAG, and filling row by row is already a topological order. One pass, O(R·C), no priority queue. If moves could go up or left too, cycles appear and you need Dijkstra.

Left: cell costs. Right: best total so far. Green: the route recovered from the corner.

03Obstacles, memory, and the shared skeleton

Real grids have walls. A blocked cell simply gets ways = 0 (or dp = ∞ for costs), and the same rule carries on around it. Watch the base cases: a wall in the first row blocks every cell to its right.

You also rarely need the whole table. Row i only reads row i−1 and the cell to its left, so one array of length C is enough: row[j] += row[j−1] for counting, or row[j] = grid + min(row[j], row[j−1]) for costs. Memory drops from O(R·C) to O(C).

This “2D table, each cell from its top, left or diagonal neighbour” skeleton is the most common shape in DP. You will meet it again in knapsack, LCS and edit distance; only the meaning of the cells and the combine rule change.

Cost at a glance

Fill an R × C gridO(R·C)

Memory with one rolling rowO(C)

Recover the routeO(R + C)

Remember

With moves only right or down, each cell depends on its top and left neighbours: add them to count paths, take the min to find the cheapest.
Filling row by row is a topological order of this DAG, so no queue or Dijkstra is needed.
Because a row only reads the previous row, one array of length C replaces the whole table.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Each new dp cell looks only up and left. After the fill, follow the green route back from the corner. Try your own grid, e.g. 1 3 1 / 1 5 1 / 4 2 1.

Interactive visualizerfocus here, then space ← →

Grid values

	0	1	2	3	4
0	3	7	9	2	7
1	9	8	3	5	5
2	1	7	9	8	5
3	3	8	6	4	10

dp: minimum path sum (down/right only)

	0	1	2	3	4
0	3	·	·	·	·
1	·	·	·	·	·
2	·	·	·	·	·
3	·	·	·	·	·

Minimum path sum, moving only right or down. Start cell dp[0][0] = 3.

Pseudocode

 1 dp[0][0] = grid[0][0] 2 first row/col: only one way in (forced path) 3 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) 4 trace back from the corner along the cheaper predecessor

1 / 1

Check

Three questions. Pick an answer to see why.

On a 3 × 3 grid (right/down moves), how many paths reach the bottom right corner?

The cell at row 0, column 2 is a wall in a grid for counting paths. What are ways[0][3] and ways[0][4]?

If moves in all four directions were allowed, which method finds the cheapest path?

Practice

Real problems to lock it in, easiest first.

LeetCodeUnique Paths intermediate↗LeetCodeMinimum Path Sum intermediate↗LeetCodeUnique Paths II intermediate↗CSESGrid Paths I intermediate↗LeetCodeDungeon Game advanced↗