Unique Path II

出处

现在考虑网格中有障碍物，那样将会有多少条不同的路径？

网格中的障碍和空位置分别用1和0来表示。

样例

如下所示在3x3的网格中有一个障碍物：
[
[0,0,0],
[0,1,0],
[0,0,0]
]
一共有2条不同的路径从左上角到右下角。

注意

m和n均不超过100

Solution

这里需要注意的是处理有障碍物时的情况，即直接表示为零，然后按照同样的方式进行累加。而因为要从第一个元素进行处理，所以需要注意如果还是用 result[j] = result[j] + result[j-1] 在 j==0 时会出现 result[-1] 的情况，就不符合题目意思了，所以在边界需要特别处理一下

Complexity

时间复杂度 O(n)，空间复杂度 O(n)

Code

class Solution:
    """
    @param obstacleGrid: An list of lists of integers
    @return: An integer
    """
    def uniquePathsWithObstacles(self, obstacleGrid):
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        result = [1] * n
        for i in range(n):
            if obstacleGrid[0][i] == 1:
                for j in range(i, n):
                    result[j] = 0

        for i in range(1, m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    result[j] = 0
                elif j != 0:
                    result[j] = result[j] + result[j-1]

        return result[-1]