Count a robot's routes across a grid moving only right or down. Each cell's count is the cell above plus the cell to the left.
▼The problem
LeetCode 62 (Medium). A robot starts in the top-left corner of an m × n grid and can only move right or down. How many different paths reach the bottom-right corner?
Example (LeetCode's): m = 3, n = 7 → 28.
1 1 1 1 1 1 1 1 2 3 4 5 6 7 1 3 6 10 15 21 28TRY IT ON LEETCODE ▶
The solution
def uniquePaths(m, n):
row = [1] * n # top street
for r in range(1, m):
for c in range(1, n):
row[c] += row[c - 1] # above + left
return row[-1]Transcript
Unique Paths. A robot starts in the top left corner of a grid, and can only move right or down. How many different paths reach the bottom right corner?
Take a grid three rows tall and seven columns wide. Every path makes six moves right and two moves down, in some order. That gives twenty-eight paths.
The naive way walks every path. From each corner, try right, then try down, and count the arrivals. The paths branch at every step, so the work grows exponentially, and the same corners get walked again and again.
Here's the key. To reach any corner, the last move came from the corner above, or the corner to the left. So the paths here are the paths above, plus the paths to the left. Along the top row and the left column, there's only one way: straight along the edge.
In code, keep one row of counts, all ones for the top street. For each next row, walk left to right: each cell adds the count on its left to the count it already holds from above. The last cell is the answer.
Let's fill it. The top row is all ones. Second row: one, two, three, four, five, six, seven. Third row: one, then three, six, ten, fifteen, twenty-one, and finally, twenty-eight.
Every corner is filled once, so the time is order m times n, and one row is order n space. There is a closed form: choose which two of the eight moves go down. Twenty-eight again.
Above plus left, corner by corner. That's Unique Paths.