The problem
A robot stands in the top-left cell of an m × n grid and must reach the bottom-right cell, moving only down or right. Return the number of different paths.
Examples
- Input
m = 3, n = 7
- Output
28
- Input
m = 3, n = 2
- Output
3
Constraints
- 1 ≤ m, n ≤ 100
- The answer is at most 2 × 10⁹.
The idea
The table way: the paths into a cell are the paths into the cell above plus those into the cell to its left — Pascal’s triangle, m × n steps. But the table has a closed form.
Every path is exactly m − 1 moves down and n − 1 moves right, in some order; choosing which of the m + n − 2 moves are the downs fixes the path. That is the binomial coefficient C(m + n − 2, m − 1) — “m + n − 2 choose m − 1”. For a 3 × 7 grid: C(8, 2) = 8 × 7 ÷ 2 = 28. Multiplying in and dividing one factor at a time keeps every intermediate value a whole number, since after step i it equals C(·, i).
- Time
- O(min(m, n))
- Space
- O(1)
Solution · every language run against every case
class Solution: def uniquePaths(self, m: int, n: int) -> int: # Every path is m - 1 moves down and n - 1 moves right, in some order. Choosing which # of the m + n - 2 moves go down fixes the path: C(m + n - 2, k), k the smaller count. k = min(m, n) - 1 total = m + n - 2 ways = 1 for i in range(1, k + 1): ways = ways * (total - k + i) // i # exact at every step: it equals C(total - k + i, i) return ways