Unique Paths

A robot sits at the top-left corner of an m by n grid. It can move only right or down, one cell at a time, and must reach the bottom-right corner. Count the number of distinct paths.

Example#

For a 3 by 7 grid the answer is 28. For a 3 by 2 grid the answer is 3: down-down-right, down-right-down, and right-down-down.

Brute force note#

Recursively branching at each cell into “go right” and “go down” explores an exponential tree, recomputing the path count for shared cells many times.

Optimal approach#

The number of ways to reach a cell equals the ways to reach the cell above it plus the ways to reach the cell to its left, since those are the only two entry moves. Cells in the first row and first column each have exactly one path. Fill a single row of counts left to right and roll it down each row: dp[c] += dp[c-1] accumulates the “from left” and “from above” contributions in place.

 1def unique_paths(m, n):
 2    dp = [1] * n
 3    for _ in range(1, m):
 4        for c in range(1, n):
 5            dp[c] += dp[c - 1]
 6    return dp[-1]
 7
 8
 9print(unique_paths(3, 7))  # 28
10print(unique_paths(3, 2))  # 3
11print(unique_paths(1, 1))  # 1

Complexity#

Time is O(m times n): each cell is computed once. Space is O(n) using a single rolling row instead of a full O(m times n) grid. A closed-form binomial coefficient also exists, but the DP is clearer to derive.

This is a 2D grid DP compressed to one dimension. Study grid recurrences on the dynamic programming topic page, then continue through the 60-day curriculum.