描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

Python

不断迭代终点，与不同路径1的区别在于增加了障碍 = 1时 return 0

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if not len(obstacleGrid) or not len(obstacleGrid):return 0
        cache = {} # 缓存减少所用时间
        m = len(obstacleGrid) - 1 # m和n分别代表终点横纵坐标
        n = len(obstacleGrid[0]) - 1 
        return self.pathHelper(obstacleGrid,m,n,cache)
        
    def pathHelper(self,obstacleGrid,m,n,cache):
        if (m,n) in cache:
            return cache[(m,n)]
        elif m<0 or n<0 or obstacleGrid[m][n]==1:
            return 0
        elif m==0 and n==0:
            return 1
        
        cache[(m,n)] = self.pathHelper(obstacleGrid,m-1,n,cache) + self.pathHelper(obstacleGrid,m,n-1,cache)
        return cache[(m,n)]