LeetCode 63. 不同路径 II
题目描述
题意分析
机器人从网格左上角出发，到右下角结束，每步只能向右或向下移动一格。
0表示可走格子，1表示障碍，不能进入或穿过障碍。返回不同移动路径的数量，不是判断能否到达，也不是求最短长度。起点或终点被阻挡时没有合法路径；方向限制使机器人不能向上、向左绕回障碍后方。
解法：一维动态规划
核心思路
[!blue]
设一个格子的状态为“从起点走到这里的路径数”。非障碍格的最后一步只能来自正上方或正左方，两类路径的最后一步不同，不会重复计数，因此当前路径数等于上方路径数与左方路径数之和。障碍格不可到达，状态必须为零，不能接收任何方向的贡献。
按行从左向右计算时，只依赖上一行同列和当前行前一列，可以用一维
dp代替整个二维表。处理(row, col)之前，dp[col]尚未更新，保存上方的旧状态；dp[col - 1]已在本行更新，保存左方的新状态。非障碍时相加，就得到当前格的路径数。开始只令
dp[0] = 1，表示到达起点有一条尚未移动的初始路径，其余位置为零。如果起点本身是障碍，循环会立即将它清零。首行通过左侧逐步传递，首列仅继承上方；一旦遇到障碍，对应状态归零，后续不会凭空恢复为一。障碍分支与累加分支必须互斥。遇到障碍后清零并结束当前格的处理，既抹去来自上方的旧值，也阻止接入左侧路径。
解题步骤
- 创建长度为列数的零数组
dp，只在最初设置一次dp[0] = 1。- 从上到下遍历各行，每行从左到右处理各列。
- 当前格是障碍时将
dp[col]置零；否则若存在左侧格子，执行dp[col] += dp[col - 1]。- 第一列没有左侧来源，非障碍时保留上方传来的值，无需单独补一。
- 全部行处理完后，返回右下角对应的
dp[cols - 1]。
代码实现
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int cols = obstacleGrid[0].length;
int[] dp = new int[cols];
dp[0] = 1;
for (int row = 0; row < obstacleGrid.length; row++) {
for (int col = 0; col < cols; col++) {
if (obstacleGrid[row][col] == 1) {
// 障碍格不可到达，路径数必须清零。
dp[col] = 0;
} else if (col > 0) {
// 当前位置旧值来自上方，左边已是当前行的路径数。
dp[col] += dp[col - 1];
}
}
}
return dp[cols - 1];
}
}
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
cols := len(obstacleGrid[0])
dp := make([]int, cols)
dp[0] = 1
for row := 0; row < len(obstacleGrid); row++ {
for col := 0; col < cols; col++ {
if obstacleGrid[row][col] == 1 {
// 当前格有障碍时，来自上方和左方的路径都不能进入。
dp[col] = 0
} else if col > 0 {
// 当前位置旧值来自上方，左边已是当前行的路径数。
dp[col] += dp[col-1]
}
}
}
return dp[cols-1]
}
复杂度分析
- 时间复杂度：$O(mn)$，
m、n分别为行数、列数，每个格子只执行常数次状态更新。- 空间复杂度：$O(n)$，只保存一行的路径数，输入网格不修改。
关键点总结
[!green]
- 按最后一步来自上方或左方分类，路径集合互不重叠，因此可以相加。
- 一维压缩保留的是上方旧值和左方新值，更新方向必须与这个含义对应。
- 障碍格清零，起点只注入一次初始路径，边界便能在统一循环中处理。
易错点总结
[!yellow]
- 障碍格清零后仍然累加左侧，会重新给障碍赋予路径，使路径穿过不能进入的位置。
- 每一行都重设
dp[0] = 1，会让首列被障碍截断后的格子重新变得可达。- 从右向左更新，读到的左侧还是上一行状态，不再符合来自当前行左方的转移。
- 将全部
dp初始为一，会给未经过起点的状态添加虚假的路径贡献。- 起点或终点有障碍时仍返回正数，说明没有让障碍清零规则覆盖边界格子。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 62. 不同路径 | 中等 | 路径方向相同，增加障碍后，障碍格的方案数必须为0。 |
| 64. 最小路径和 | 中等 | 同样从上方和左方转移，本题加方案数，原题取最小路径代价。 |
| 120. 三角形最小路径和 | 中等 | 在网格上从前驱状态递推路径；本题遇障碍时清零可达路径，该题按三角形相邻位置求最小路径。 |
| 931. 下降路径最小和 | 中等 | 在网格上从前驱状态递推路径；本题遇障碍时清零可达路径，该题允许来自上一行三个相邻列。 |
| 980. 不同路径 III | 困难 | 不同路径系列，都有障碍格。III 额外要求覆盖全部空格且每格仅访问一次，不能直接沿用单调方向 DP。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！