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 * 109.
Example 1:
Input: m = 3, n = 7 Output: 28
Example 2:
Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
- Right -> Down -> Down
- Down -> Down -> Right
- Down -> Right -> Down
1 <= m, n <= 100
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# Create a 2D DP table with default value 0
dp = [[0] * n for _ in range(m)]
# Initialize the first row and first column
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
# Fill the DP table
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]O(m * n): The time complexity is linear with respect to the number of cells in the grid since we iterate through each cell once to compute its value based on its neighbors.
O(m * n): The space complexity is also linear with respect to the number of cells due to the use of a 2D list to store the number of ways to reach each cell.
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m > n:
m, n = n, m # Ensure that we use less space
dp = [1] * m
for j in range(1, n):
for i in range(1, m):
dp[i] += dp[i - 1]
return dp[-1]In this optimized version, the space complexity is reduced to O(min(m, n)), making it more efficient when one dimension of the grid is much smaller than the other.