python实现leetcode之63. 不同路径 II

解题思路

简单动态规划，思路与63题完全一致
不同之处是障碍物处的方案数为0

63. 不同路径 II

代码

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        dp = [[0 for col in row] for row in obstacleGrid]
        for i in range(len(dp)):
            for j in range(len(dp[i])):
                if obstacleGrid[i][j]: dp[i][j] = 0
                elif i == 0 and j == 0: dp[i][j] = 1
                elif i == 0: dp[i][j] = dp[i][j-1]
                elif j == 0: dp[i][j] = dp[i-1][j]
                else: dp[i][j] = dp[i-1][j] + dp[i][j-1]
                
        return dp[-1][-1]