Problem Statement
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 10^9.
Example Inputs and Outputs
- Input:
m = 3, n = 7
Output: 28
- Input:
m = 3, n = 2
Output: 3
Explanation: There are 3 ways to reach the bottom-right corner:
- Right → Down → Down
- Down → Down → Right
- Down → Right → Down
Grid Representation (3x7 example)
Movement Rules
Simple Example (2x3 grid)
How DP Works (3x3 example)
Path Calculation Logic
Approach
Dynamic Programming
Steps
- Create a recursive function
f(i, j, dp) to calculate the number of paths to cell (i, j):
- If the robot is at the first row or first column, there is only one path (
1).
- Use a memoization table
dp to store intermediate results.
- Recursively calculate the number of paths to
(i, j) using:
up = f(i-1, j, dp)left = f(i, j-1, dp)
- Use a top-down approach starting from
(m-1, n-1) and return the result.
Time & Space Complexity
- Time Complexity:
O(m * n) because we solve each subproblem once.
- Space Complexity:
O(m * n) due to the memoization table.
Code Snippet
Dry Run
Input: m = 3, n = 2
Initialization:
dp = [[-1, -1], [-1, -1], [-1, -1]]
Recursive Calls:
f(2, 1) calls f(1, 1) and f(2, 0).f(1, 1) calls f(0, 1) and f(1, 0).- Base cases return:
f(0, 1) = 1f(1, 0) = 1f(2, 0) = 1
- Combine results:
f(1, 1) = 1 + 1 = 2f(2, 1) = 2 + 1 = 3
Final dp table:
Output: 3
Complexity Analysis
Conclusion
The dynamic programming approach significantly reduces redundant computations by storing intermediate results in a memoization table. This optimization ensures the solution is efficient for large grids, making it suitable for practical applications. Always prefer efficient methods to handle scalability in problem-solving.