机器人到达终点的不同路径数

"不同路径 II 是一个典型的动态规划问题，主要涉及算法和数据结构的知识，特别是二维网格的处理。此问题要求计算一个机器人从网格的左上角到达右下角的不同路径数量，其中路径受到障碍物的影响。" 在这个问题中，我们首先需要理解题目给出的约束条件和输入格式。`obstacleGrid` 是一个 `m x n` 的二维数组，其中 `0` 表示可通行的位置，`1` 表示障碍物。机器人只能向下或向右移动，不能穿越障碍物。 ### 问题解析 **动态规划方法** 动态规划是一种有效解决此类问题的方法，通过建立状态转移方程来逐步解决问题。我们可以定义一个二维数组 `f`，其中 `f[i][j]` 表示到达 `(i, j)` 位置的路径数量。初始化时，如果 `(0, 0)` 位置没有障碍物，那么 `f[0][0]` 应该是 `1`，因为只有一条从起始点到达该位置的路径（不移动）；否则，`f[0][0]` 应该是 `0`，因为有障碍物无法通过。 接下来，我们可以通过遍历整个网格来填充 `f` 数组。对于每个位置 `(i, j)`： 1. 如果 `i == 0`（在第一行），机器人只能从上一行到达，因此 `f[i][j]` 等于上一行相同列的位置 `f[i-1][j]`。如果 `j == 0`（在第一列），机器人只能从左边到达，所以 `f[i][j]` 等于上一行相同列的位置 `f[i][j-1]`。 2. 对于其他位置，机器人可以来自上方或左侧。因此，`f[i][j]` 将是这两个值的和，但需要减去那些经过障碍物的路径（如果 `obstacleGrid[i][j]` 是 `1`，则路径数量为 `0`）。 ### 代码实现 ```cpp class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int n = obstacleGrid.size(), m = obstacleGrid.at(0).size(); vector<int> f(m); f[0] = (obstacleGrid[0][0] == 0); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (obstacleGrid[i][j] == 1) { f[j] = 0; } else if (i > 0 && j > 0) { f[j] = f[j - 1] + (i > 0 ? f[i - 1][j] : 0); } } } return f[m - 1]; } }; ``` 这段代码首先初始化了第一列的路径数，然后根据当前位置是否为障碍物更新 `f[j]`。对于非边界位置，`f[j]` 的值等于它左边和上边的路径数之和（如果有障碍物，路径数为 `0`）。最后，返回右下角的 `f[m - 1]` 即为结果。 ### 示例分析 对于示例1，我们有以下的网格： ``` 0 0 0 0 1 0 0 0 0 ``` 从左上角到右下角的合法路径有两种：`向右 -> 向右 -> 向下 -> 向下` 和 `向下 -> 向下 -> 向右 -> 向右`。因此，输出是 `2`。 对于示例2： ``` 0 1 0 0 ``` 机器人必须先向下移动，然后向右移动，只有一条路径，所以输出是 `1`。 ### 时间和空间复杂度 时间复杂度是 `O(m * n)`，因为我们需要遍历整个网格一次。空间复杂度也是 `O(m)` 或 `O(n)`，取决于我们是否只存储一行或一列的前向路径。 ### 总结 不同路径 II 的问题通过动态规划提供了一种高效且简洁的解决方案。理解如何构建状态转移方程和正确初始化边界条件是解决这类问题的关键。这个算法不仅可以应用于计算网格路径，还可以扩展到其他需要计算多步决策问题的场景。