Unique Paths
MediumGrid DP · dp[i][j] = dp[i−1][j] + dp[i][j−1]
Paths to a cell = paths from the cell above + paths from the cell to the left.
The idea
A robot moving only right or down reaches a cell from the cell above or the cell to the left. So the number of paths to each cell is the sum of those two neighbors.
1
1
1
1
1
1
1
1
1
Step 1 of 6. Top row and left column have exactly 1 path. Every other cell = paths from above + from the left.
1/6
Optimal
timeO(n·m)spaceO(m)
Row-rolling sums.
1const row = Array(n).fill(1);2for (let i = 1; i < m; i++)3 for (let j = 1; j < n; j++)4 row[j] += row[j - 1];5return row[n - 1];Input
- grid
- 3 × 3
Memory
- at
- —
- cells marked
- 5
Output
- paths
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- m = 3, n = 7
- Output:
- 28
- Explanation:
- 28 distinct right/down routes across the grid.
Example 2
- Input:
- m = 3, n = 2
- Output:
- 3
- Explanation:
- 3 ways down a 3x2 grid.
Example 3
- Input:
- m = 1, n = 5
- Output:
- 1
- Explanation:
- One straight row → a single path.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.