Easy · Grid DP
Understand → Visualise → Practice.
A robot moves only right or down from the top-left to bottom-right of a rows-by-cols grid. Return the number of distinct paths.
The number of ways to reach a cell is the ways to reach the cell above plus the ways to reach the cell to its left. The first row and column have one way each.
Every cell in the top row can only be reached by moving right, so it has 1 path.
Row by row, dp[col] += dp[col − 1]; the old dp[col] is the value from above.
The last cell of the final row holds the answer.
O(rows × cols) time and O(cols) space.
Boundary cells have one path, not zero.
Read the full guide first: Dynamic Programming.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.