medium, dynamic programming

Question

接Unique Paths
加入路徑上有一些障礙物，又該如何求解。
障礙物在矩陣中標(biāo)記為1，其他標(biāo)記為0

For example,
中間是障礙物的3X3網(wǎng)格如下
[
[0,0,0],
[0,1,0],
[0,0,0]
]
總共有2條路徑.

Note: m and n will be at most 100.

Solution

與Unique Paths解法類似，因?yàn)锽ottom-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]