打卡群刷题总结0717——不同路径 II

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if len(obstacleGrid) == 0 or len(obstacleGrid[0]) == 0:
            return 0
        width, length = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[1] * length for i in range(width)]

        flag = False
        for i in range(width):
            if obstacleGrid[i][0] == 1:
                flag = True
            if flag:
                dp[i][0] = 0

        flag = False
        for j in range(length):
            if obstacleGrid[0][j] == 1:
                flag = True
            if flag:
                dp[0][j] = 0

        for i in range(1, width):
            for j in range(1, length):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j]  = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]