Grid DP Example: The Cheapest Route Through a Toll Grid

A grid table finds the cheapest route as readily as it counts routes: each cell holds its own cost plus the cheaper of the two cells it can be entered from, and walking back from the corner recovers the route. The surface is a road map of tolls, where the reader must see that taking the cheapest next road is not the same as taking the cheapest route.

A driver crosses a city laid out as a 3 by 3 grid of districts, from the top-left to the bottom-right, moving only east or south, and pays each district's toll on entering it, the first included. The tolls, row by row, are 1 1 8, then 4 9 9, then 1 1 1. The state is cheapest[r][c], the least total toll to reach district (r, c), and cheapest[r][c] = toll[r][c] + min(cheapest[r − 1][c], cheapest[r][c − 1]), with a missing neighbour treated as unreachable. A run filled the table row by row.

The cheapest crossing costs 8. To find the route, start at the corner and step back to whichever neighbour holds the smaller total: from 8 to 7 on the west, from 7 to 6 on the west, from 6 to 5 on the north, and from 5 to the start. Read forwards, the route is south, south, east, east, paying 1 + 4 + 1 + 1 + 1 = 8, which the run printed.

The run also tried the driver's instinct, entering the cheaper of the two next districts each time. That goes east into the toll of 1, then east into 8 because 8 beats 9, then south twice: 1 + 1 + 8 + 9 + 1 = 20. The first move looked best and led into the expensive corner of the map. The table avoids that because each cell holds the best total over every route into it, not the best single step.

The pattern to take away: when a grid problem asks for the most or the least along a monotone route, keep the same table as for counting and change the sum into a maximum or minimum. The answer sits in the corner, and the route is read back by retracing, at each cell, the neighbour that won.