63. 不同路径 II

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