The cheapest way down through the grid

A grid of non-negative numbers is a toll board. Starting at the top left and finishing at the bottom right, moving only right or down, report the smallest total you can pay. Every cell you step on, including the first and the last, is paid.

Worked example#

1 3 1
1 5 1
4 2 1

The cheapest route is 1 → 3 → 1 → 1 → 1, going right, right, down, down, and it totals 7. Going down the left side costs 1 + 1 + 4 + 2 + 1 = 9.

The idea#

There are a lot of routes: choosing where to put the downs among the rights gives a number that grows like two to the power of the grid's size. Trying them all is hopeless on anything but a tiny board.

But look at the last cell. You can only arrive there from above or from the left. So:

cheapest(bottom right) = cell's own toll
                       + the smaller of cheapest(above) and cheapest(left)

And the same is true of every cell. That is the whole solution. Each cell needs the answer for the two cells touching it from above and left, so if you fill the grid top to bottom and left to right, both are always ready when you need them.

best[r][c] = grid[r][c] + min(best[r-1][c], best[r][c-1])

The first row can only be reached from the left, and the first column only from above, so those are filled with running totals.

Why this is not greedy#

Always stepping toward the cheaper neighbour looks reasonable and is wrong. A cheap step can lead into an expensive region, and nothing local tells you that.

1 8 6
0 9 1
3 9 0

Greedy starts at the 1, sees 8 to the right and 0 below, and steps down. From there it is walled in by nines and pays 13. The cheapest route goes right across the top, 1 → 8 → 6 → 1 → 0, which is 11. Paying the 8 early is what makes it cheap.

Greedy commits. Filling the table commits to nothing until every cell's answer is known.

What it costs#

One pass over the grid, a constant amount of work per cell, so rows times columns. The exponential number of routes is never enumerated because each cell's answer is computed once and reused by both cells it feeds.

That reuse is the entire idea behind dynamic programming, and a grid is the easiest place to see it, because the table of answers is shaped exactly like the problem.

Constraints#

• 1 <= rows, columns <= 500
• 0 <= grid[r][c] <= 1000