29 Dec 62. Unique Paths
There is a robot on an
m x n grid. The robot is initially located at the top-left corner (i.e.,
grid). 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
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.
Input: m = 3, n = 7 Output: 28
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: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down
1 <= m, n <= 100
class Solution: def uniquePaths(self, m: int, n: int) -> int: # Initialize the first row and column to 1 # Since the combination for # dp[i] = dp[i-1] # dp[j] = dp[j-1] # dp[i][j] = dp[i-1][j] + dp[i][j-1] # df_table = [*n] + [ + *(n-1) ] * (m-1) # Since dp[i][j] only depends on the calculated cells before, # we can simply initialize the value of all cells to 1. dp = [*n] * m for r in range(1, m): for c in range(1, n): dp[r][c] = dp[r - 1][c] + dp[r][c - 1] return dp[-1][-1]