264. Corner to Corner Paths
A cleaning robot is parked on the top-left tile of a floor made of m rows and n columns of square tiles. It must reach the bottom-right tile, and each step moves it exactly one tile either to the right or down; it never leaves the floor and never moves back.
Return how many different routes the robot can take. The input is chosen so that the answer never exceeds 2000000000, so it fits a signed 32-bit integer. A 1 x 1 floor has exactly one route (stay put). Intended time is O(min(m, n)) with a multiplicative binomial, or O(m*n) with a table, and O(1) or O(n) space.
Example 1
- Input:
- m = 4, n = 6
- Output:
- 56
- Explanation:
Any route has 3 down moves and 5 right moves in some order, so C(8,3) = 56 routes exist.
Example 2
- Input:
- m = 1, n = 9
- Output:
- 1
- Explanation:
A single row forces eight right moves, so only one route exists.
Example 3
- Input:
- m = 17, n = 18
- Output:
- 1166803110
- Explanation:
C(33,16) = 1166803110 routes, near the largest value allowed by the guarantee.
Constraints
1 ≤ m, n ≤ 100
The number of routes is guaranteed to be at most 2 * 109.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(min(m, n))
- Space
- O(1)