63. Unique Paths II

在 62 题的基础上添加了障碍这一概念,给定一个矩阵,0代表可通行,1代表不可通行,机器人在左上角,每次向下或者向右移动,到达右下角的路径数

同样是动规,只不过障碍所在的点直接给0就可以了

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        mat = [[0 for i in range(n)]for j in range(m)]
        mat[0][0] = 1 - obstacleGrid[0][0]
        for j in range(1, n):
            mat[0][j] = mat[0][j-1] and (1 - obstacleGrid[0][j])
        for i in range(1, m):
            mat[i][0] = mat[i-1][0] and (1 - obstacleGrid[i][0])
        for i in range(1, m):
            for j in range(1, n):
                if not obstacleGrid[i][j]:
                    mat[i][j] = mat[i-1][j] + mat[i][j-1]
                else:
                    mat[i][j] = 0
        return mat[m-1][n-1]