A robot stands in the top-left cell of a grid with m rows and n columns. Each move takes it
one cell to the right or one cell down.
Return the number of different paths that take it to the bottom-right cell.
Example 1
- Input
- m = 2, n = 3
- Output
- 3
Example 2
- Input
- m = 3, n = 4
- Output
- 10
Constraints
- 1 ≤
m,n≤ 100 - The answer is less than 2³¹.
Show the pattern
Dynamic programming (2D)
Every path into a cell arrives from the cell above it or the cell to its left, so each cell's count is the sum of two neighbouring counts: a 2D table filled row by row.
See dynamic programming (2d) in a visualiserShow the approach
Let paths[r][c] be the number of ways to reach cell (r, c). The last move into it came from the
cell above or the cell to the left, so paths[r][c] = paths[r − 1][c] + paths[r][c − 1]. Cells
in the top row or the left column can only be reached one way.
Fill the table row by row. Each row needs only the row above, so keep a single row: going left
to right, row[c] += row[c − 1] adds the count from the left to the count from above, which is
what row[c] still holds. The answer is the last cell.
(Counting directly also works: every path is m − 1 downs and n − 1 rights in some order, so the answer is the binomial coefficient C(m + n − 2, m − 1).)
Time: O(m × n) · Space: O(n)