Unique Paths in a Grid
mediumSave
CombinatoricsDynamic ProgrammingMatrix
Given a grid of dimensions m x n, find the number of unique paths from the top-left corner to the bottom-right corner. You can only move either down or right at any point in time.
Example 1
Input
[ 2, 3 ]
Output
3
Explanation. From a 2x3 grid (2 rows, 3 columns), the paths can be: right-right-down, right-down-right, down-right-right.
Example 2
Input
[ 3, 3 ]
Output
6
Explanation. From a 3x3 grid, the paths can be: right-right-down-down, right-down-right-down, right-down-down-right, down-right-right-down, down-right-down-right, down-down-right-right.
Example 3
Input
[ 1, 1 ]
Output
1
Explanation. From a 1x1 grid, there is only one cell and hence only one path, which is to stay at the initial position.
Follow-up: What if some cells are blocked and you cannot move through them?
Constraints:
1 <= m, n <= 100
- Views
- 4