Lesson 29.3 · DP on Grids
Filling Backwards, Squares, and Two Walkers
Some 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
Think of it like this
Planning how much water to carry on a hike: you work backwards from the summit, asking at each point how much you must have on arrival to make it from there.
1.Three useful twists
Backwards (Dungeon Game): the health you need at a cell depends on what comes after it, not before. Fill from the bottom-right: need[r][c] = max(1, min(need[r + 1][c], need[r][c + 1]) − dungeon[r][c]).
Squares (Maximal Square): dp[r][c] = side of the largest all-ones square whose bottom-right corner is (r, c) = 1 + min(top, left, top-left) when the cell is 1. Each neighbour limits how far the square can extend.
Two walkers (Cherry Pickup II): two robots move down one row at a time. The state is (row, column of robot 1, column of robot 2), with 9 move combinations per step. When both are in the same cell, its cherries count once.
Quick check
For Maximal Square, why the minimum of three neighbours?
Remember
- Fill direction follows dependencies.
- Square: 1 + min of three.
- Multiple walkers → bigger state, same idea.
Common mistakes
- Filling Dungeon Game forwards (the forward state can't capture future requirements).