题目
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
解题思路
- 数学方法，m*n的方格一共需要走
m+n-2步，其中m-1步向下，一共走法是组合数C(m+n-2,m-1) - 动态规划，dp[i][j]表示走到(i,j)的走法数，dp[i][j] = dp[i-1][j] + dp[i][j-1]
代码
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
return math.factorial(m + n - 2) // math.factorial(m - 1) // math.factorial(n - 1)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[-1]
