Day39 动态规划2
62.不同路径
思路
dp[m,n]表示第（m, n）格总共有dp[m,n]条不同的路径
递推公式由（m - 1, n）格（m, n - 1）格的路径之和得出
初始化，应该初始化最上面一行和最左边一列
尝试写代码：
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * n for _ in range(m)]
for i in range(m):
dp[i][0] = 1
for i in range(n):
dp[0][i] = 1
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[m - 1][n - 1]
成功通过！
总结
注意创建二维数组时[[0] * n for _ in range(m)]第一个n表示列，第二个m表示行
63. 不同路径 II
思路
整体思路与上一题类似，只是如果当前的dp[i,j]左边或者上边有障碍物，那么该路径为没有障碍物的格子的路径数
或者遇到障碍物后，该位置的dp为0
问题，如果只有一行，或者一列，初始化的时候需要注意，不能够初始化为1
如果初始化的时候，碰到障碍物，那之后的也都为0，不需要初始化
递推公式的时候也注意，只有当前格子没有障碍的的时候才计算dp，否则保持0
尝试写代码：
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[0] * n for _ in range(m)]
for i in range(m):
if obstacleGrid[i][0] == 0:
dp[i][0] = 1
else:
break
for i in range(n):
if obstacleGrid[0][i] == 0:
dp[0][i] = 1
else:
break
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 0:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
成功通过！
