0063. Unique Paths II¶
题目信息¶
- 题号:
不同路径 II
- 难度:
Medium
- 主题:
动态规划、网格、障碍、滚动数组
- 原题:
- 重点:
从递归统计剩余路径,推导到障碍清零的一维路径状态
题目重述¶
给定一个 m × n 网格 obstacleGrid,其中 0 表示可通行单元格,1 表示障碍。
机器人从左上角 (0,0) 出发,每一步只能向右或向下移动一格。
返回机器人到达右下角 (m-1,n-1) 且不进入任何障碍格的不同路径数量。若起点或终点是障碍,
答案为 0。
约束为 1 <= m, n <= 100,并保证最终答案不超过 2 * 10^9。
自建示例¶
输入:
[[0,0,0,0],
[0,1,0,0],
[0,0,1,0]]
输出:2
两条合法路径分别沿第一行到达最右列,或先进入 (1,2) 再向右;它们都避开两个障碍。
输入:[[1,0,0]]
输出:0
起点是障碍,机器人无法进入网格。
输入:[[0,0,1,0,0]]
输出:0
网格只有一行,障碍切断了起点与终点之间的唯一通道。
C++ 实现¶
#include <algorithm>
#include <vector>
class Solution {
private:
static constexpr int LIMIT = 2'000'000'001;
int cappedAdd(int first, int second) {
return static_cast<int>(
std::min<long long>(
LIMIT,
static_cast<long long>(first) + second
)
);
}
int memoDfs(
const std::vector<std::vector<int>>& grid,
int row,
int column,
std::vector<std::vector<int>>& memo
) {
if (row < 0 || column < 0 || grid[row][column] == 1) {
return 0;
}
if (row == 0 && column == 0) {
return 1;
}
int& cached = memo[row][column];
if (cached != -1) {
return cached;
}
cached = cappedAdd(
memoDfs(grid, row - 1, column, memo),
memoDfs(grid, row, column - 1, memo)
);
return cached;
}
int memoizedSearch(const std::vector<std::vector<int>>& grid) {
const int rows = static_cast<int>(grid.size());
const int columns = static_cast<int>(grid[0].size());
std::vector<std::vector<int>> memo(
rows,
std::vector<int>(columns, -1)
);
return memoDfs(grid, rows - 1, columns - 1, memo);
}
int tableDp(const std::vector<std::vector<int>>& grid) {
const int rows = static_cast<int>(grid.size());
const int columns = static_cast<int>(grid[0].size());
std::vector<std::vector<int>> ways(
rows,
std::vector<int>(columns, 0)
);
ways[0][0] = grid[0][0] == 0 ? 1 : 0;
for (int row = 0; row < rows; ++row) {
for (int column = 0; column < columns; ++column) {
if (grid[row][column] == 1) {
ways[row][column] = 0;
continue;
}
if (row == 0 && column == 0) {
continue;
}
const int fromAbove =
row > 0 ? ways[row - 1][column] : 0;
const int fromLeft =
column > 0 ? ways[row][column - 1] : 0;
ways[row][column] = cappedAdd(fromAbove, fromLeft);
}
}
return ways[rows - 1][columns - 1];
}
int rollingDp(const std::vector<std::vector<int>>& grid) {
const int rows = static_cast<int>(grid.size());
const int columns = static_cast<int>(grid[0].size());
std::vector<int> ways(columns, 0);
ways[0] = grid[0][0] == 0 ? 1 : 0;
for (int row = 0; row < rows; ++row) {
for (int column = 0; column < columns; ++column) {
if (grid[row][column] == 1) {
ways[column] = 0;
} else if (column > 0) {
ways[column] = cappedAdd(
ways[column],
ways[column - 1]
);
}
}
}
return ways[columns - 1];
}
public:
int uniquePathsWithObstacles(
std::vector<std::vector<int>>& obstacleGrid
) {
return rollingDp(obstacleGrid);
}
};
题解¶
递归状态¶
先从终点反向思考。到达开放格 (row,column) 的最后一步只能来自上方或左方,因此路径数满足:
paths(row, column)
= paths(row - 1, column)
+ paths(row, column - 1)
越过网格边界或落在障碍格时返回 0;到达开放的起点时返回 1,表示尚未移动也构成一条有效前缀。
直接递归会从不同移动顺序反复计算同一格,重复子问题随网格增大迅速增加。
记忆化复用¶
memoizedSearch 为每个坐标保存一次递归结果。状态只由当前位置决定,与此前采用哪条路径到达无关,
所以同一格的后续计算可以安全复用。
每个开放格最多展开一次,递归搜索由指数规模降为 O(mn)。这一版保留了递归定义,下一步可以按依赖顺序
直接填表,消除递归栈。
二维路径状态¶
定义:
ways[row][column]
= 从起点到达当前格的合法路径数量
扫描顺序为从上到下、从左到右。计算当前格时,上方和左方已经完成,因此开放格直接把两个来源相加。 两类路径的最后一步方向不同,互不重叠;任何到达当前格的路径又必属于其中一类,所以转移没有遗漏或重复。
障碍清零¶
障碍格不能作为路径终点,也不能把此前路径继续传播到右方或下方,因此它的状态必须写成 0。
在一维状态中,ways[column] 进入当前格前仍保存上方路径数。若障碍格不清零,这个旧值会被错误带到
同一行右侧以及下一行。覆盖为 0 正好切断所有穿过该障碍的路径。
起点开放时初始化为 1;起点是障碍时初始化为 0。第一行或第一列一旦遇到障碍,状态归零后会自然
向后传播,不需要单独预填整行或整列。
状态演化¶
以中央存在一个障碍的网格为例:
网格: 路径数:
0 0 0 1 1 1
0 1 0 -> 1 0 1
0 0 0 1 1 2
障碍格归零后,其右侧只能接收上方路径,障碍下方只能接收左方路径。终点的两条路径分别从障碍的上方和 下方绕行。
一维滚动¶
二维转移只依赖上一行同列和当前行左侧,可以把状态压缩为一行。逐行从左向右更新时:
更新前的
ways[column]表示上方路径数;已更新的
ways[column - 1]表示左方路径数;开放格执行两者相加;
障碍格把当前列覆盖为
0。
从左向右的顺序使同一个数组同时保存两类依赖。若反向更新,左侧状态仍属于上一行,便不再对应当前格的 真实左方来源。
饱和计数¶
题目只保证最终答案不超过 2 * 10^9。在大型开放区域中,中间格路径数仍可能先超过该范围,随后又被
障碍完全切断。直接使用 32 位加法会在这些无效的大状态处溢出。
代码把超过上限的状态统一截为 LIMIT = 2,000,000,001。所有转移只有非负加法和障碍清零。若一个已超过
上限的状态仍存在通往终点的后缀,那么该状态的每条不同前缀都能接上同一后缀,最终路径数也会超过题目上限。
因此在题目保证成立时,这类状态必然无法贡献到终点;对它进行饱和不会改变最终精确答案。
方法关系¶
记忆化递归直接保存递归定义中的坐标答案;二维动态规划按照依赖顺序主动计算全部坐标;滚动数组继续观察到 每轮只需要上一行,于是删除更早的状态。
三种方法使用相同的路径计数不变量,区别只在求值顺序和状态存储范围。公开入口调用 rollingDp,保留
O(mn) 时间并把辅助空间降为 O(n)。
复杂度分析¶
设网格大小为 m × n:
记忆化递归时间为
O(mn),备忘录为O(mn),递归栈最深为O(m+n);二维动态规划时间为
O(mn),辅助空间为O(mn);一维滚动动态规划时间为
O(mn),辅助空间为O(n)。
饱和加法只增加常数时间。起点、终点、单行和单列网格都由同一初始化与障碍清零规则覆盖。