Grid DP: cells filled from their neighbours
When moves only go right and down, each cell's answer comes from the cell above and the cell to the left. Fill row by row.
The pattern
On a grid where movement only goes right and down (or the shape being measured grows only one way), a cell's answer depends on a fixed set of neighbours that are already filled if you go row by row:
Grid DP
dp[r][c]
- = cell value ⊕ opt(dp[r − 1][c], dp[r][c − 1]) for paths;
- = 1 + min(up, left, up-left) for the largest square ending here.
boundary
- the first row and column, or an extra row and column of identity values.
When the grid allows moves in all four directions, the dependency graph has cycles and this pattern does not apply: that is a shortest-path problem (Dijkstra or breadth-first search).
Worked example: the minimum path sum
Cell costs [[1,3,1,2],[1,5,1,3],[4,2,1,1]]; moves right or down.
-
Step 1 / 12
Base cases filled first.
-
Step 2 / 12
(0, 1): 3 + min(—, 1) = 4.
-
Step 3 / 12
(0, 2): 1 + min(—, 4) = 5.
-
Step 4 / 12
(0, 3): 2 + min(—, 5) = 7.
-
Step 5 / 12
(1, 0): 1 + min(1, —) = 2.
-
Step 6 / 12
(1, 1): 5 + min(4, 2) = 7.
-
Step 7 / 12
(1, 2): 1 + min(5, 7) = 6.
-
Step 8 / 12
(1, 3): 3 + min(7, 6) = 9.
-
Step 9 / 12
(2, 0): 4 + min(2, —) = 6.
-
Step 10 / 12
(2, 1): 2 + min(7, 6) = 8.
-
Step 11 / 12
(2, 2): 1 + min(6, 8) = 7.
-
Step 12 / 12
(2, 3): 1 + min(9, 7) = 8. The cheapest path costs 8.
Variations
- Obstacles: a blocked cell contributes 0 ways.
- Largest square of 1s: the square ending at (r, c) is limited by the three squares ending above, left and diagonally.
- Dungeon: when health must stay positive, fill from the target backwards, because the requirement at a cell depends on what comes after.
The problems in this module: