Unique Grid Paths with Right and Down Moves
A robot starts in the top-left cell of an m x n grid and must reach the bottom-right cell. From each cell, the robot may move exactly one cell either right or down.
Return the total number of different paths the robot can follow to reach the destination.
Method Signature
int uniquePaths(int m, int n)
m is the number of rows in the grid.n is the number of columns in the grid.- Return the number of unique paths from the top-left cell to the bottom-right cell.
Movement Rules
- The robot begins at row
0, column 0.
- The destination is row
m - 1, column n - 1.
- The robot may move only one cell right or one cell down.
- The robot must remain inside the grid.
- Two paths are different if their sequences of movements are different.
Constraints
1 <= m <= 1001 <= n <= 100- The number of unique paths is at most
1,000,000,000.
Examples
Example 1
uniquePaths(m = 4, n = 4)
Output: 20
The robot must make three right moves and three down moves. These movements can be arranged in 20 different valid orders.
Example 2
uniquePaths(m = 2, n = 5)
Output: 5
The robot makes one down move and four right moves. The down move can appear in any one of five positions.
Example 3
uniquePaths(m = 1, n = 8)
Output: 1
Because the grid has only one row, the robot has exactly one path to the destination.