63 Unique Paths II

稍微加了一个obstacle, 使用类似的动态规划，也可以得到解。

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        row = len(obstacleGrid)
        column = len(obstacleGrid[0])
        if row == 0 or column == 0:
            return 0
        dp = [[0 for j in range(column)]for i in range(row)]
        if obstacleGrid[0][0] == 1:
            return 0
        else:
            dp[0][0] = 1
        ## dp initialization
        for i in range(1, row):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = dp[i-1][0]
            else:
                dp[i][0] = 0
        for j in range(1,column):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = dp[0][j-1]
            else:
                dp[0][j] = 0
        for i in range(1, row):
            for j in range(1, column):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                    continue
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[row-1][column-1]