2-D Dynamic Programming Paths in a grid
538. Unique Paths
A robot stands in the top-left cell of a grid with m rows and n columns. Each move takes it one cell
down or one cell to the right. It cannot move up, left or diagonally.
Return the number of different paths that take the robot to the bottom-right cell. Two paths are different if they make their moves in a different order.
The count grows very fast, so return it modulo 109 + 7, that is, the remainder after dividing it by 1,000,000,007.
Example 1
Input: m = 3, n = 4
10Explanation: Every path makes 2 moves down and 3 moves right. Two of the 10 paths are right, right, right, down, down, and down, right, down, right, right.
Example 2
Input: m = 1, n = 5
1Explanation: The grid is a single row, so the only path moves right four times.
Example 3
Input: m = 1000, n = 1000
965601742Explanation: The exact count has 600 digits. 965601742 is its remainder after dividing by 1,000,000,007.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ m, n ≤ 1000
Clarifying questions
What you would ask an interviewer before writing any code.