63. 不同路径 II

解1 递归

dfs深度优先
超出时间限制

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        
        if obstacleGrid == []:
            return 0
        
        if obstacleGrid[0][0] == 1:
            return 0
        
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        if obstacleGrid[m - 1][n - 1] == 1:
            return 0
        
        result = list()
        self.dfs(obstacleGrid, 0, 0, result)
        return sum(result)
        
        
    def dfs(self, obstacleGrid, i, j, result):
        
        if i == len(obstacleGrid) - 1 and j == len(obstacleGrid[0]) - 1:
            result.append(1)
            
        elif i == len(obstacleGrid) - 1:
            if obstacleGrid[i][j + 1] == 1:
                return
            else:
                self.dfs(obstacleGrid, i, j + 1, result)
                
        elif j == len(obstacleGrid[0]) - 1:
            if obstacleGrid[i + 1][j] == 1:
                return
            else:
                self.dfs(obstacleGrid, i + 1, j, result)
        
        else:
            if obstacleGrid[i][j + 1] == 0:
                self.dfs(obstacleGrid, i, j + 1, result)
                
            if obstacleGrid[i + 1][j] == 0:
                self.dfs(obstacleGrid, i + 1, j, result)

解2 动态规划

参考62

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        
        if obstacleGrid == []:
            return 0
        
        # 机器人所在位置为障碍物 无法开始
        if obstacleGrid[0][0] == 1:
            return 0
        
        # 终点为障碍物 无法到达
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        if obstacleGrid[m - 1][n - 1] == 1:
            return 0
        
        # 动态规划
        path = [[1 for i in range(n)] for j in range(m)]
        
        # 若第1列 有一个方格为障碍物 那么相当于它下面的方格都为障碍物
        for i in range(1, m):
            if obstacleGrid[i-1][0]:
                obstacleGrid[i][0] = 1
        
        # 同理 第一行有一个为障碍物 右边的方格都为障碍物
        for j in range(1, n):
            if obstacleGrid[0][j - 1]:
                obstacleGrid[0][j] = 1
            
        
        for i in range(1, m):
            for j in range(1, n):
                
                
                if (obstacleGrid[i - 1][j] and obstacleGrid[i][j - 1]) or obstacleGrid[i][j]:
                    # 上 左 都无法到达 或 本身就是障碍
                    path[i][j] = 0
                    
                elif obstacleGrid[i - 1][j]:
                    # 上 为障碍物
                    path[i][j] = path[i][j - 1]
                    
                elif obstacleGrid[i][j - 1]:
                    # 左 为障碍物
                    path[i][j] = path[i - 1][j]
                    
                else:
                    # 上 左 都可到达
                    path[i][j] = path[i][j - 1] + path[i - 1][j]
                    
        return path[m - 1][n - 1]