Paths Through a Grid
You get two integers m and n. They describe a grid with m rows and n columns.
You start in the top-left cell and want to reach the bottom-right cell. In one move you can go one cell right or one cell down. You cannot move up, move left, or leave the grid.
Return the number of different paths from the start cell to the end cell. Two paths are different if they visit a different list of cells.
Note
If the grid is a single cell (m = 1 and n = 1), you are already at the end. That counts as 1 path.
Hint
To enter a cell, you must come from the cell above it or the cell to its left. So the number of paths to a cell is the sum of the paths to those two cells. The cells in the first row and the first column each have exactly 1 path.
Examples
Example 1
- Input:
- 2, 3
- Output:
- 3
Each path makes 2 moves right (R) and 1 move down (D). The three orders are R R D, R D R and D R R.
Example 2
- Input:
- 4, 4
- Output:
- 20
Each path makes 3 moves right and 3 moves down. There are 20 ways to choose which 3 of the 6 moves go right.
Example 3
- Input:
- 1, 7
- Output:
- 1
With only one row, you can only move right. There is exactly one path.
Constraints
1 <= m <= 251 <= n <= 25- The answer is always smaller than
2^53, so it fits in a normal JavaScript number.
Run checks your code against the 3 examples. Submit checks it against all 223 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.