赞
踩
dp[i][j]
是到达位置 (i, j)
的不同路径数dp[i][j] = dp[i-1][j] + dp[i][j-1]
,想要到达 (i, j)
只有两种方法
(i-1, j)
,然后向右移动(i, j-1)
,然后向下移动i, j
,dp[i][0] = 1, dp[0][j] = 1
,其余位置均为 0(无所谓初始化为多少)
class Solution: def uniquePaths(self, m: int, n: int) -> int: # dp[i][j] represents the number of ways to reach the position (i, j) dp = [[0 for j in range(n)] for i in range(m)] # initialization: all positions in the first row and column can be reached uniquely for i in range(m): dp[i][0] = 1 for j in range(n): dp[0][j] = 1 # dp formula # since it can only go down or right, either iteration over row or column first can work 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[-1][-1]
本题可以用数论直接分析出结果:对于
m
×
n
m\times n
m×n 的网格,必然需要
m
+
n
−
2
m+n-2
m+n−2 步,其中有
m
−
1
m-1
m−1 步是向下走的,所以所有路径的总数是
C
m
+
n
−
2
m
−
1
\mathcal{C}_{m+n-2}^{m-1}
Cm+n−2m−1
要注意,计算组合的时候不能直接计算分子、分母然后相除,而是要在计算分子时不断除以分母,防止溢出。
另外,图论中的深度搜索似乎也可以完成:将路径看成二叉树的话,遍历所有的叶子节点即可。然而这棵树的深度是 m + n − 1 m+n-1 m+n−1,意味着复杂度是 O ( 2 m + n ) O(2^{m+n}) O(2m+n),所以会直接超时,因为其中绝大部分的遍历都是没有意义的。
dp[i][j]
是到达位置 (i, j)
的不同路径数if obstacleGrid[i][j] == 0: dp[i][j] = dp[i-1][j] + dp[i][j-1]
,想要到达 (i, j)
只有两种方法(如果当前位置没有障碍的话)
(i-1, j)
,然后向右移动(i, j-1)
,然后向下移动i, j
,dp[i][0] = 1, dp[0][j] = 1
,其余位置均为 0;本题中,如果行/列中存在一个障碍,则障碍之后的所有位置都都应该初始化为 0(无法到达)
class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: m, n = len(obstacleGrid), len(obstacleGrid[0]) # dp[i][j] represents the number of ways to reach position (i, j) # if the position (i, j) has an obstacle, there is 0 way to reach this position dp = [[0 for i in range(n)] for j in range(m)] # initialization: all positions in the first row and column can be reached uniquely for i in range(m): if obstacleGrid[i][0] or (i > 0 and dp[i-1][0] == 0): dp[i][0] = 0 else: dp[i][0] = 1 for j in range(n): if obstacleGrid[0][j] or (j > 0 and dp[0][j-1] == 0): dp[0][j] = 0 else: dp[0][j] = 1 # dp formula for i in range(1, m): for j in range(1, n): if obstacleGrid[i][j]: dp[i][j] = 0 else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[-1][-1]
本题的初始化中,“障碍之后的位置无法到达”也是个坑。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。