Unique Paths
MediumDynamic Programming
A robot starts on the top-left cell of a grid with m rows and n columns and wants to reach the bottom-right cell. Each move takes it exactly one cell right or one cell down; it can never move left or up or leave the grid.
Return the number of distinct paths the robot can take. Two paths are different if their sequences of moves differ.
Example 1
- Input:
- m = 3, n = 4
- Output:
- 10
- Explanation
- Every path makes exactly 2 down moves and 3 right moves. A path is decided by which 2 of its 5 moves are the downs, and there are 10 ways to choose them.
Example 2
- Input:
- m = 2, n = 5
- Output:
- 5
- Explanation
- There is exactly one down move, and it can happen in any of the 5 columns, so there are 5 paths.
Example 3
- Input:
- m = 1, n = 6
- Output:
- 1
- Explanation
- With a single row the robot can only keep moving right, so there is just 1 path.
Constraints
1 <= m, n <= 100- The answer is at most
2 * 10^9