DP on Grids & the Zone Crossing
In short: on a grid where the van only moves right or down, every zone's
answer depends only on the zone above it and the zone to its left, and both
are already finished by the time you get there. So the grid doubles as the
table: no separate structure, no recursion, just a fill order where "above"
and "left" come first. Swap + for min and the same shape counts routes or
finds the cheapest one; closed zones become 0 routes or infinite cost so the
combine step quietly ignores them.
![A 3x3 cost grid for [[1,3,1],[1,5,1],[4,2,1]], each cell showing its running cost with arrows from above and left into the bottom-right corner 7, and the winning RRDD path traced in green](/api/assets/dsa/assets/fdab48196afb6ce5.png)
Meridian divides the city into a grid of service zones. Each zone has a congestion toll, and on any given morning a few are closed for roadworks. A van leaving the north-west depot for the south-east one works its way across the grid, and dispatch wants two numbers: how many routes are there, and which one is cheapest?
A grid needs no separate table. If the van only ever moves right or down, every zone can be reached only from the zone above it or the zone to its left, and those two zones already have their answers when you get there. The map is the table, and the only question left is the order you fill it in.
Counting routes
Every route into a zone arrives from above or from the left, and no route does both. So the counts simply add:
ways[r][c] = ways[r - 1][c] + ways[r][c - 1]
A closed zone has zero routes into it, and every count downstream quietly loses the routes that would have used it. Watch a 4 × 5 district fill with two zones closed (X):
Every cell on one anti-diagonal (r + c constant) depends only on the diagonal before it, so the answers sweep across the grid as a wavefront from the start corner.
The start has one route, the empty one. The two closed zones will stay at zero routes. 4 by 5 table. At row 0, column 0 — value 1. 3 of 20 cells filled.
The wavefront shows why the fill order is safe: a cell only ever reads cells on the diagonal before it. Row by row is one order that respects this, and column by column is another:
R, C = 3, 3
ways = [[1] * C for _ in range(R)]
for c in range(1, C): # columns outside,
for r in range(1, R): # rows inside
ways[r][c] = ways[r - 1][c] + ways[r][c - 1]
print(ways[R - 1][C - 1])The counts grow fast. Guess before you run it:
ways = [[1] * 10 for _ in range(10)]
for r in range(1, 10):
for c in range(1, 10):
ways[r][c] = ways[r - 1][c] + ways[r][c - 1]
print(ways[9][9])You only ever read the row above, so one row is enough. Step through the rolling
version, where each row[c] already holds "above" and gains "left":
The cheapest crossing
Swap + for min and add the zone's own toll, and the counting table becomes a
cost table:
cost[r][c] = grid[r][c] + min(cost[r - 1][c], cost[r][c - 1])
A closed zone gets infinity, and min then ignores it. Using 0 for a
closed zone is a trap, and so is reusing the -1 from the map as if it were a
toll:
The centre zone is closed, so the only legal routes go round the edge, and the cheaper one costs 15. This prints 9 because it drives straight through the roadworks and gets paid for it. Make closed zones unreachable.
Now fill the cost table yourself. Every frame shows the two cells a zone compares.
Change the tolls, or close a different zone with -1, and run it again:
Your cost table. Each zone reads only its upper and left neighbours, both already final, and closed zones stay at infinity so min passes them over.
Reading the route back
The table holds costs, not moves, so you recover the route by walking back from the corner. At each zone, ask which neighbour the minimum came from, and step there. When the two neighbours tie, you need a rule, or two correct programs will print different routes. The zone crossing uses "came from above" on a tie, which makes the returned route hug the top edge for as long as it can:
When one number per cell isn't enough
Some questions can't be answered from "the cheapest way to reach this zone". Here's one, written the way an interviewer would hand it to you:
Interview-style problem: the articulated truck. A truck crosses a toll grid from the top-left zone to the bottom-right one, moving right or down. It pays every zone's toll, plus
turn_feeevery time it switches between moving right and moving down. Return the lowest total.Constraints: 1 to 30 rows and columns, tolls 0 to 100,
turn_fee0 to 1,000.Examples:
[[1, 1, 1], [5, 5, 1], [5, 5, 1]]with fee 10 →15(right, right, down, down: one turn). The same grid with fee 0 →5, the plain cheapest route.
The cheapest arrival at a zone might have come in moving down, while a slightly dearer one came in moving right and can carry on without paying for a turn. Keep one number per cell and you have to throw one of them away, and it may be the one you needed. The fix is the most important idea in this section: when the future depends on something, put it in the state. Here that's the last direction, so each zone carries two numbers. In the capstone exercise, a driver with emergency permits carries one number per permits-used count. The grid stays the same, each cell holds a little more, and the fill order doesn't change because every dependency still points up or left.
❓ Cross-question: "What if the van can also move up or left?" Then two neighbouring zones depend on each other, and no fill order finishes one before the other. It stops being a table problem and becomes a shortest-path problem on a graph of zones, and Dijkstra settles zones in cost order, which is exactly the order the table no longer gives you.
How fast do routes pile up?
The number of right/down routes across an n by n block of moves is C(2n, n), while the table has only (n + 1)² cells:
| n | routes | table cells |
|---|---|---|
| 5 | 252 | 36 |
| 10 | 184,756 | 121 |
| 12 | 2,704,156 | 169 |
| 15 | 155,117,520 | 256 |
Listing routes is exponential and filling the table is quadratic, which is why nobody enumerates routes to find the cheapest one.
Every cell does one + or min of its two finished neighbours, and there are
R · C cells, so the plain grid is O(R · C) time. The table itself is
O(R · C) space; since a cell only ever reads the row above and the row
it's building, one rolling row is enough and that drops space to O(C) — the
same trade as knapsack's rolling row, and for the same reason: you can fill
the number this way, but you lose the ability to walk the route back.
| Grid question | Cell holds | Combine | Time |
|---|---|---|---|
| how many routes | a count | + |
O(R · C) |
| cheapest route | a cost | min + toll |
O(R · C) |
| largest free square | a side length | 1 + min of three |
O(R · C) |
| with a turn fee | a cost per last direction | min over 2 |
O(R · C · 2) |
with k permits |
a cost per permits used | min per layer |
O(R · C · k) |
Idioms & real-world patterns
Guard the edges, don't trust negative indices
cost[r - 1][c] at r = 0 is cost[-1][c], the bottom row, and Python
reads it without complaint. On a counting grid it's usually still 0 and the bug
hides. On a cost grid it's usually infinity and the bug hides too, until
someone prefills the table differently. Write if r > 0 and if c > 0
explicitly, or pad the table with a sentinel row and column.
⚡ Advanced: the anti-diagonal is parallel
Every cell on one anti-diagonal is independent of the others, so a GPU or a vectorised library can compute a whole diagonal at once. Sequence alignment in bioinformatics uses the same wavefront to fill enormous grids in parallel.
Quick practice
R, C = 3, 3
closed = {(1, 1)}
ways = [[0] * C for _ in range(R)]
for r in range(R):
for c in range(C):
if (r, c) in closed:
continue
if r == 0 and c == 0:
ways[r][c] = 1
else:
up = ways[r - 1][c] if r > 0 else 0
left = ways[r][c - 1] if c > 0 else 0
ways[r][c] = up + left
print(ways[2][2])The cheapest crossing of this grid costs 7, but this prints 3 because row 0 reads `cost[-1][c]`, the bottom row, instead of having no "above" at all. Guard the read with `r > 0`.
🎯 Your turn
Write cheapest_crossing(grid). grid[r][c] is a zone's toll, or -1 for
closed. The van moves right or down from the top-left zone to the bottom-right
one and pays every toll it enters, including the first and last. Return
{"cost": total, "path": "RRDD…"}, or None if every route is blocked.
cheapest_crossing([[1, 3, 1], [1, 5, 1], [4, 2, 1]])→{"cost": 7, "path": "RRDD"}
Ties: walk back from the corner and step up whenever the cell above costs less than or equal to the cell on the left.
Then press ▶ Run, tap the Live App try chips, and hit ✓ Check. Green means the zone crossing is built. ✅