LeetCode 63 不同路径 II

题目链接：

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

以下是使用Go语言实现外观数列问题的代码：

func uniquePathsWithObstacles(obstacleGrid [][]int) int { m, n := len(obstacleGrid), len(obstacleGrid[0]) // 初始化 dp 数组 dp := make([][]int, m) for i := 0; i < m; i { dp[i] = make([]int, n) } // 初始化第一行和第一列 for i := 0; i < m && obstacleGrid[i][0] == 0; i { dp[i][0] = 1 } for j := 0; j < n && obstacleGrid[0][j] == 0; j { dp[0][j] = 1 } // 计算 dp 数组 for i := 1; i < m; i { for j := 1; j < n; j { if obstacleGrid[i][j] == 1 { dp[i][j] = 0 } else { dp[i][j] = dp[i-1][j] dp[i][j-1] } } } return dp[m-1][n-1] }

执行用时：4 ms, 在所有 Go 提交中击败了41.88%的用户

内存消耗：2.4 MB, 在所有 Go 提交中击败了42.34%的用户

通过测试用例：41 / 41

解题思路：

本题是一道动态规划问题，可以使用动态规划的方法求解。我们定义一个 dp 数组，其中 dp[i][j] 表示机器人从网格左上角走到位置 (i, j) 时的路径总数。由于机器人只能向下或向右走，因此对于网格中的任意一点 (i, j)，机器人要么从上方的位置 (i-1, j) 走过来，要么从左侧的位置 (i, j-1) 走过来。因此我们有动态转移方程：

dp[i][j] = dp[i-1][j] dp[i][j-1]

注意，由于我们的坐标系是从 0 开始计数的，因此在代码实现时，我们需要将 dp 数组的第一行和第一列初始化为 1，这是因为机器人只能向下或向右移动，因此从起点到第一行或第一列中的任意一点的路径数都为 1。

另外，由于题目中给定的网格中可能存在障碍物，因此在计算 dp 数组时，需要特别处理障碍物。如果在位置 (i, j) 上有障碍物，则 dp[i][j] 的值应该为 0，因为机器人不能走到这个位置。此外，由于第一行和第一列的值是由障碍物左侧和上侧的格子计算而来的，因此如果第一行或第一列中存在障碍物，则障碍物后面的格子都无法到达，对应的 dp 值应该全部初始化为 0。

最终，dp 数组右下角的值就是机器人从起点走到终点的路径总数。

代码中首先定义了 dp 数组，然后依次初始化第一行和第一列的值。接着，使用两层循环遍历整个网格，计算 dp 数组中的每个元素。如果当前位置 (i, j) 上有障碍物，则将 dp[i][j] 的值设置为 0，否则根据动态转移方程计算 dp[i][j] 的值。最后，返回 dp 数组右下角的值，即机器人从起点走到终点的路径总数。

时间复杂度分析：

对于一个 m x n 的网格，我们需要计算 dp 数组中的每个元素，因此时间复杂度是 O(mn)。