63. 不同路径 II

https://leetcode-cn.com/problems/unique-paths-ii/

解法一：回溯（超时）

先递归右边块，再递归下方块，遇到1则终止返回，若能到达终点，路径数+1.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        self.count = 0  #全局变量，记录路径总数
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        #边界条件，由于只对右边和下方块检测，对（0，0）块没有检测，若该块有路障，直接返回
        if obstacleGrid[0][0] == 1:  
            return self.count
        self.travel(obstacleGrid, 0, 0, m, n)
        return self.count

    def travel(self, obstacleGrid, row, col, m, n):    #递归函数
        #下标越界或遇到障碍
        if row >= m or col >= n or obstacleGrid[row][col] == 1:
            return
        if row == m-1 and col == n-1:  #到达终点，路径+1
            self.count += 1           
        self.travel(obstacleGrid, row, col+1, m, n)    #递归右侧
        self.travel(obstacleGrid, row+1, col, m, n)    #递归下方

解法二：dp

遍历棋盘，若(i, j)位置为路障‘1’，直接将dp[i][j]置为0，表示此路不通，其余同62.不同路径 的dp，方程为dp[i][j] = dp[i-1][j] + dp[i][j-1]。

边界：第一行和第一列，包括最左上角(0, 0)。若(0, 0)为0，则dp[0][0]=1，否则dp[0][0]=0

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)  #行数
        n = len(obstacleGrid[0])  #列数
        path = [[0] * n for _ in range(m)]  #状态表
        #初始化
        path[0][0] = int(obstacleGrid[0][0] == 0)  #（0，0）号元素
        #第0列
        for i in range(1, m):
            if obstacleGrid[i][0] == 1:
                path[i][0] == 0
            else:
                path[i][0] = path[i-1][0]
        #第0行
        for j in range(1, n):
            if obstacleGrid[0][j] == 1:
                path[0][j] == 0
            else:
                path[0][j] = path[0][j-1]
        #其余部分
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:  #遇到路障
                    path[i][j] == 0
                else:
                    path[i][j] = path[i][j-1] + path[i-1][j]
        return path[m-1][n-1]

2020.3.29

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        n = len(obstacleGrid)
        m = len(obstacleGrid[0])
        dp = [[1] * m for _ in range(n)]
        #初始条件
        dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0  #起点
        for j in range(1, m):     #填第一行        
            if obstacleGrid[0][j] == 1 or dp[0][j-1] == 0:
                dp[0][j] = 0
        for i in range(1, n):   #填第一列
            if obstacleGrid[i][0] == 1 or dp[i-1][0] == 0:
                dp[i][0] = 0
        for i in range(1, n):
            for j in range(1, m):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[n-1][m-1]