題目：

一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標記為“Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為“Finish”）。
現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-paths-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
輸入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
輸出: 2

解答：

思路：新建dp數(shù)組與原數(shù)組尺寸相同,dp[i][j]位置為幾條路徑可達i, j位置，因為只有向下和向右2種路徑可走，那么可以知道，如果左邊點有1條路可達，上面點有2條路可達，那么dp[i][j]則有3條路可達。
所以狀態(tài)轉(zhuǎn)移方程可為：
dp[i][j] = dp[i][j-1] + dp[i-1][j]
代碼如下：

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        
        dp = [[0]*n for _ in range(m)]

        #特判
        if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
            return 0
        else:
            dp[0][0] = 1
        #第一行
        for j in range(1, n):
            if obstacleGrid[0][j] != 1:
                dp[0][j] = dp[0][j-1]

        # 第一列
        for i in range(1, m):
            if obstacleGrid[i][0] != 1:
                dp[i][0] = dp[i-1][0]

        #剩余的
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] != 1:
                    dp[i][j] = dp[i][j-1] + dp[i-1][j]
        
        return dp[-1][-1]