LeetCode 63. Unique Paths II

题目

思路

动归+滚动数组

代码

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