Count the Paths Across a Grid

Counting the paths across a grid that moves only right or down is a table with one entry per cell, where each entry is the sum of the entry above and the entry to the left. This walkthrough fills that table for a grid with a blocked cell and reads the count from the bottom-right corner.

A warehouse robot starts in the top-left cell of a floor 3 rows by 5 columns and must reach the bottom-right cell, moving one cell right or one cell down at a time. A pallet blocks the cell in row 1, column 2, counting from 0. The state is paths[r][c], the number of routes from the start to cell (r, c). The last move into a cell came either from above or from the left, and those routes do not overlap, so paths[r][c] = paths[r − 1][c] + paths[r][c − 1]. A blocked cell has 0 routes, and a missing neighbour off the edge counts as 0.

The corner holds 6, as a run printed, and the same grid with no pallet gives 15. The table has rows × columns entries and each takes one addition, so the count costs O(rows × columns) time. Each row reads only itself and the row above, so one row of five numbers, updated left to right, is enough space.

A blocked cell does not need a special rule in the recurrence: it is a 0, and every cell beside it adds that 0 in. The same table answers related questions by changing one thing. Allowing a diagonal move adds a third term, and asking for the cheapest route instead of the number of routes replaces the sum with a minimum, as Grid DP Example: The Cheapest Route Through a Toll Grid shows.