62. 不同路径
https://leetcode-cn.com/problems/unique-paths/
解法一:计算组合数
长为m,宽为n,从起点到终点一共m-1+n-1
步。从m-1+n-1中选m-1步,剩下的n-1步中再选n-1步即可,公式为C(m-1+n-1, m-1) * C(n-1, n-1)
,复杂度O(n)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
res = 1
total = m-1 + n-1
#计算组合数
for i in range(total, m-1, -1):
res = res * i #分子累乘
for j in range(1, n):
res = res // j #分母累除
return res
解法二:dp
观察可知到达(i, j)
处只能从左边的(i, j-1)
和上边的 (i-1, j)
得到,没有别的方式,因此DP方程为P[i][j] = P[i - 1][j] + P[i][j - 1]
。边界条件为最左列和最上一行,初始值为1,因为只有1条路到达这些地方。复杂度O(n^2)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
path = [[1]*m for _ in range(n)] #记录表
for i in range(1, n): #从第1行开始
for j in range(1, m): #从第1列开始
path[i][j] = path[i-1][j] + path[i][j-1]
return path[n-1][m-1]
2020.3.29
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m==1 or n==1:
return 1
dp = [[0] * m for _ in range(n)]
for i in range(1, n):
dp[i][0] = 1
for j in range(1, m):
dp[0][j] = 1
for i in range(1, n):
for j in range(1, m):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[n-1][m-1]
最后更新于