Unique Paths II

medium, dynamic programming

Question

接Unique Paths
加入路径上有一些障碍物，又该如何求解。
障碍物在矩阵中标记为1，其他标记为0

For example,
中间是障碍物的3X3网格如下
[
[0,0,0],
[0,1,0],
[0,0,0]
]
总共有2条路径.

Note: m and n will be at most 100.

Solution

与Unique Paths解法类似，因为Bottom-Up的解法比Top-Down的解法更简单，这里使用Bottom-Up的方法。

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