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.
class Solution: # Dynamic Programming # Time: O(m * n) # Space: O(min(m, n)) def unique_paths(self, m: int, n: int) -> int: if m > n: m, n = n, m dp = [1] * m for _ in range(1, n): for j in range(1, m): dp[j] += dp[j - 1] return dp[m - 1]class SolutionMath: # Math solution: C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!) # Time: O(min(m, n)) # Space: O(1) def unique_paths(self, m: int, n: int) -> int: # Total moves: (m-1) right + (n-1) down = m+n-2 # Choose (m-1) positions for right moves out of (m+n-2) total if m > n: m, n = n, m # Optimize for smaller factorial result = 1 for i in range(m - 1): result = result * (n + i) // (i + 1) return result
