Module 29
DP on Grids
When the state is a cell: counting paths, cheapest paths, squares of ones, filling in reverse, rolling rows, and two walkers at once.
Many DP problems live on a grid where you can only move in some directions, usually right and down. Each cell's answer depends on the cells you could have come from, so you fill the table row by row and read the answer from a corner.
This module covers counting paths (with and without obstacles), minimum-cost paths, triangles and falling paths, the largest square of ones, problems that must be filled backwards from the goal, keeping only one row of memory, and a state with two walkers moving together.
Best after: DP Foundations: 1D
Part 1
Learn the ideas
- 29.1Counting and Costing PathsIf moves are right and down, a cell is reached from above or from the left: dp[r][c] = combine(dp[r − 1][c], dp[r][c − 1]).14 min
- 29.2Saving Memory: One Row Is EnoughWhen a cell needs only the row above and the cell to its left, a single 1D array updated left to right holds both.8 min
- 29.3Filling Backwards, Squares, and Two WalkersSome states depend on the future (minimum health needed from here on), so you fill from the goal. Others combine three neighbours (largest square). Two walkers moving together share one state.14 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
The basic grid DP, then the one-row version.
Obstacles zero out cells, including along the first row and column.
Cheapest path with min instead of sum of counts.
Bottom-up from the last row makes the answer land in one cell, with O(n) memory.
Three predecessors per cell (diagonals), with boundary checks.
A state that measures a shape: the largest square ending at each cell.
Filling backwards because the requirement depends on what comes later.
Two walkers moving together: the state is (row, column 1, column 2).