题目: 不同路径 II

分析

方法一：动态规划

我们可以定义一个二维数组dp，其中dp[i][j]表示从起点(0,0)到达位置(i,j)的不同路径数目。则对于每个位置，它的不同路径数目等于其上方和左侧的路径数之和。由于存在障碍物，所以我们需要特判当前位置是否为障碍物，如果是则dp[i][j]=0。动态规划的边界条件为：当i=0或j=0时，dp[i][j]的值始终为1，因为此时只有一条路径可以到达该位置。

以下是Python的实现代码：

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                elif i == 0 and j == 0:
                    dp[i][j] = 1
                elif i == 0:
                    dp[i][j] = dp[i][j-1]
                elif j == 0:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

方法二：递归回溯

我们可以使用递归回溯的方法，从起点开始逐步探索所有可能的路径。对于每个位置，我们可以向右或向下前进，直到到达终点。如果当前位置是障碍物，或者已经到达了边界，则返回0。如果到达了终点，则返回1。最后将所有的路径数目相加即为答案。

以下是Python的实现代码：

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        self.count = 0
        self.backtrack(obstacleGrid, 0, 0)
        return self.count
    
    def backtrack(self, grid, i, j):
        m, n = len(grid), len(grid[0])
        if i == m or j == n or grid[i][j] == 1:
            return
        if i == m-1 and j == n-1:
            self.count += 1
            return
        self.backtrack(grid, i+1, j)
        self.backtrack(grid, i, j+1)

方法三：组合数学

我们可以将整个问题转化为一个组合数学问题，即从起点到终点的不同路径数目等于从起点到终点的所有可能路线数目除以所有不可能的路线数目。不可能的路线包括穿过障碍