###### tags: `Leetcode` `medium` `dynamic programming` `python`

# 63. Unique Paths II

## [題目連結:] https://leetcode.com/problems/unique-paths-ii/

## 題目:
You are given an ```m x n``` integer array ```grid```. There is a robot initially located at the **top-left corner** (i.e., ```grid[0][0]```). The robot tries to move to the **bottom-right corner** (i.e., ```grid[m-1][n-1]```). The robot can only move either down or right at any point in time.

An obstacle and space are marked as ```1``` or ```0``` respectively in ```grid```. A path that the robot takes cannot include **any** square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to ```2 * 10**9```.


#### [圖片來源:] https://leetcode.com/problems/unique-paths-ii/

## 解題想法:
兄弟題目: [62. Unique Paths](/PkGJvaCWR0ae78I5zaz_BA)

* 此題給的數組中，"1"表示障礙物，要求避開障礙物的情況下從左上走到右下
* dp[i][j]表示從左上走到(i,j)有幾種方法數

* 想法:
* Step1:初始判斷
* 若左上or左下有障礙物，無法到達
* return 0
* Step2:初始dp
* 將左上dp[0][0]=1 (一種走法)
* Step3:往下重新定義dp左邊邊界
* 若有障礙物=0 else 繼承上一格的走法數
* Step4:往右重新定義dp上面邊界
* 若有障礙物=0 else 繼承左一格的走法數
* Step5:開始dp
* **dp[i][j]**
* **0** if obstacleGrid[i][j]為障礙物
* **dp[i-1][j]+dp[i][j-1]** 該格之上+左 else

## Python:(Sol1)

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        #Step1:初始判斷
        if obstacleGrid[0][0]==1 or obstacleGrid[-1][-1]==1:
            return 0
        m=len(obstacleGrid)
        n=len(obstacleGrid[0])
        #Step2:初始dp
        dp=[[0 for _ in range(n)] for _ in range(m)]
        dp[0][0]=1
        #Step3:往下重新定義左邊邊界
        for i in range(1,m):
            dp[i][0]=0 if obstacleGrid[i][0]==1 else dp[i-1][0]
        #Step4:往右重新定義上面邊界
        for j in range(1,n):
            dp[0][j]=0 if obstacleGrid[0][j]==1 else dp[0][j-1]
        #Step5:開始dp
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=0 if obstacleGrid[i][j]==1 else dp[i-1][j]+dp[i][j-1]
        return dp[-1][-1]

## Python: (Sol2)
* 因為避免再創的二維矩陣浪費空間
* 直接使用題目的obstacleGrid matrix進行運算
* 最終return obstacleGrid[-1][-1] 即可

* 想法:
* Step1:初始判斷
* 若左上or左下有障礙物，無法到達
* return 0
* Step2:**重新定義數字**
* 將n新定義為: 到達此處可有n種走法
* 將0新定義為: 遇到障礙物，0種走法
* 將左上obstacleGrid[0][0]=1 (一種走法)
* Step3:往下重新定義左邊邊界
* 若有障礙物=0 else 繼承上一格的走法數
* Step4:往右重新定義上面邊界
* 若有障礙物=0 else 繼承左一格的走法數
* Step5:開始dp
* **obstacleGrid[i][j]**
* **0** if 該格為障礙物(除了邊界外，其餘內容都還是原本舊的數字定義: 1為障礙物)
* **該格之上+左** else

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        #Step1:初始判斷
        if obstacleGrid[0][0]==1 or obstacleGrid[-1][-1]==1:
            return 0
        #Step2:重新定義數字
        obstacleGrid[0][0]=1
        #若遇到障礙物 該格重新定義為0
        #Step3:往下重新定義左邊邊界
        for i in range(1,m):
            #若有障礙物=0 else 繼承上一格的值
            obstacleGrid[i][0] = 0 if obstacleGrid[i][0]==1 else obstacleGrid[i-1][0]
        #Step4:往右重新定義上面邊界
        for i in range(1,n):
            obstacleGrid[0][i] = 0 if obstacleGrid[0][i]==1 else obstacleGrid[0][i-1]
        #Step5:開始dp
        for i in range(1,m):
            for j in range(1,n):
                #若該格=0  if 該格為障礙物 else 該格為: 該格之上+左
                obstacleGrid[i][j]=0 if obstacleGrid[i][j]==1 else obstacleGrid[i-1][j]+obstacleGrid[i][j-1]
        return obstacleGrid[-1][-1]
    
if __name__ == '__main__':
    result = Solution()
    obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
    ans = result.uniquePathsWithObstacles(obstacleGrid)
    print(ans)