今天是紀錄LeetCode解題的第六十三天

第六十三題題目：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.

有一個機器人在m * n的網格上，機器人初始在左上角(即grid[0][0])，機器人嘗試走到右下角(grid[m - 1][n - 1])，在任何時刻機器人只能向下或向右移動

圖中障礙物表示為1，空格表示為0，機器人行走的路徑不能包含任何有障礙物的格子，返回機器人到達右下角可能的唯一路徑數量

產生的測試案例使得答案小於或等於2 * 10^9

解題思路

這題是第62題的變化題，可以先去看上一篇文章再來看這篇，在上一題我們提到該如何建構DP表，而這題我們如法炮製，只是在填表時，如果遇到障礙物，就把它當成沒辦法到該格，也就是說該格能夠抵達的路徑為0，所以我們在一開始初始化row = 0、col = 0時，只有當該格沒有障礙物且前一格有路徑可走才設為1(因為只有一條路徑，所以該格是否能抵達看前面格子能不能抵達)，其餘填表過程則只要該格沒有障礙物就套用轉移方程式(DP[row][col] = DP[row-1][col] + DP[row][col-1])即可

程式碼

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        #起點或終點有障礙物
        if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1:
            return 0
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1
        #初始化當row或col為1時且該路徑上沒有障礙物則只有一條路徑
        for i in range(1,m):
            if obstacleGrid[i][0] == 0 and dp[i-1][0] == 1: 
                dp[i][0] = 1
        for i in range(1,n):
            if obstacleGrid[0][i] == 0 and dp[0][i-1] == 1: 
                dp[0][i] = 1
        for row in range(1,m):
            for col in range(1,n):
                if obstacleGrid[row][col] == 0:
                    dp[row][col] = dp[row-1][col] + dp[row][col-1]
        return dp[m-1][n-1]

DP表格(obstacleGrid = [[0,0,1,0] , [0,0,0,0] , [0,1,0,0] , [0,0,0,0]])

• 當我們在初始化row = 0、col = 0~3時，因為col = 2有障礙物，所以無法抵達該格，這也導致col = 3時也無法抵達，所以在初始化時我們除了要檢查目前格子是否有障礙物，也要檢查前一格的DP表格中是否有路徑可以到達

• 當row = 2、col = 1時，因為該格有障礙物，所以抵達路徑為0