Grid paths: unique paths and minimum path sum

The idea: every path ends with one of two moves

A robot stands on the top-left cell of an m × n grid and wants to reach the bottom-right cell. It may only move right or down. Two classic questions: how many different paths are there, and, if each cell has a cost, which path is the cheapest? Both are solved the same way. Look at the last move into a cell: it came either from the cell above or from the cell on the left. So the answer for a cell is built from the answers of just those two cells, and the table can be filled row by row.

Counting the paths

Let paths[i][j] be the number of right-or-down paths from the start to cell (i, j). Paths that arrive from above and paths that arrive from the left are different paths, and together they are all of them, so the two counts simply add:

paths[0][0] = 1
paths[i][j] = paths[i-1][j] + paths[i][j-1]      (a neighbour off the grid counts 0)

The top row and the left column have only one neighbour each, so they are all 1. On the canvas the cell being filled is orange, the cell above is blue and the cell on the left is green. A 3 × 7 grid has 28 paths (Demo: 3 × 7 grid, count the paths).

Without obstacles there is also a formula. Every path is m + n − 2 moves, of which exactly m − 1 go down, and choosing which moves go down picks the path: C(m + n − 2, m − 1). For 3 × 7 that is C(8, 2) = 28. The table is Pascal's rule turned on its side; see Pascal's Triangle.

Obstacles

An obstacle is a cell the robot can't enter. It gets 0 paths, and the rule above does the rest: cells next to it just add 0 from that side. Two edge cases are worth seeing:

• An obstacle in the top row cuts off every cell to its right in that row: they can only be entered from the left, and the left is blocked. The same holds for the left column (Demo: an obstacle in the top row cuts off the rest of it).
• A wall across a whole row leaves no way down, so every cell below it, and the goal, has 0 paths (Demo: a wall across a whole row).

With one obstacle in the middle of a 3 × 3 grid, 6 paths drop to 2 (Demo: an obstacle in the middle). The binomial formula no longer applies; the table doesn't care.

Minimum path sum and the trace back

Now each cell has a cost (the small grey number in its corner) and the robot pays the cost of every cell it stands on, start and goal included. Let best[i][j] be the cheapest total to reach (i, j). The robot arrives from the cheaper of the two neighbours:

best[0][0] = cost[0][0]
best[i][j] = cost[i][j] + min(best[i-1][j], best[i][j-1])   (off the grid or obstacle = ∞)

The goal cell holds the answer, but not the path. To get the path, start at the goal and keep stepping to whichever neighbour, above or left, has the smaller best: that is the cell the minimum came from. The page colours that walk yellow and lists the moves and their costs (Demo: minimum path sum 7, traced back).

Why not just step to the cheaper next cell? Because a cheap first step can lead into an expensive region. On the 3 × 3 grid above, greedy pays 9 while the best path pays 7. The table compares every way into every cell, so it can't be fooled. With obstacles, an unreachable cell stays ∞ and the trace back walks around them (Demo: minimum path sum around obstacles).

Running time and memory

Each of the m·n cells is filled once from two neighbours, so both problems take Θ(mn) time. Trying every path would take C(m + n − 2, m − 1) of them, which grows exponentially. A cell only reads the row above and its own row, so a single array of length n is enough if you only want the number; the trace back needs the full table.

question	cell rule	off the grid / obstacle	answer
unique paths	top + left	0	paths[m−1][n−1]
minimum path sum	cost + min(top, left)	∞	best[m−1][n−1], then trace back

See also: 0/1 Knapsack and Edit Distance fill a two-dimensional table and trace back the same way. When moves may go in any direction, the cheapest path is a shortest-path problem: see Grid Pathfinding and Dijkstra's algorithm.

Counting paths needs only one row, updated as dp[j] += dp[j−1]: see Rolling Array Space Saving.

What the page leaves out

Moves in other directions (then the grid has cycles and needs Dijkstra or BFS instead of one pass); diagonal moves; negative costs; very large grids where the counts overflow a 64-bit integer; the one-row memory saving; counting paths modulo a prime; and editing the grid by clicking cells (the page uses fixed sample grids).

References

LeetCode 62: Unique Paths

LeetCode 63: Unique Paths II (obstacles)

LeetCode 64: Minimum Path Sum

Lattice path (Wikipedia)