python leetcode 代码随想录算法训练营第四十三天（动态规划篇）|63. 不同路径Ⅱ

63. 不同路径Ⅱ

题目链接：63. 不同路径 II - 力扣（LeetCode）

思路

如果当前网格有障碍物，那么无法到达；如果它的左边和/或上面格子有障碍物，就少了相应的到达渠道，基本思路和上道路径题一致:

代码随想录算法训练营第四十二天（动态规划篇）|62. 不同路径-CSDN博客

代码实现

import numpy as np

class Solution(object):

def uniquePathsWithObstacles(self, obstacleGrid):

m, n = np.shape(obstacleGrid)[0], np.shape(obstacleGrid)[1]

dp = np.zeros((m,n))

if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:

return 0

# 考虑第一排，障碍物右边的格子都去不了

for col in range(n):

if obstacleGrid[0][col] == 0:

dp[0][col] = 1

else:

break

# 考虑第一列，障碍物下面的各自都到不了

for row in range(m):

if obstacleGrid[row][0] == 0:

dp[row][0] = 1

else:

break

for row in range(1, m):

for col in range(1, n):

if obstacleGrid[row][col] == 1:

continue

else:

dp[row][col] = dp[row-1][col] + dp[row][col-1]

return int(dp[m-1][n-1])

金钥匙