数据结构与算法 / 系统课时
在网格中统计可行路径数量
在网格中统计可行路径数量
网格路径题的关键不是枚举所有走法,而是把“到达某个格子的方案数”作为状态。只要移动方向固定,就能从相邻已知状态递推当前位置;加入障碍物后,只需把不可到达状态清零,并正确处理首行首列边界。
学习目标
- 用二维坐标定义路径计数状态,并写出转移关系
- 正确处理起点、障碍物以及首行首列等边界
- 根据状态依赖方向确定合法的遍历顺序
从终点反推状态
设网格有 m 行、n 列,只允许向右或向下移动。定义 dp[i][j] 为从左上角起点走到坐标 (i, j) 的可行路径数量。
若当前位置不是障碍物,到达它的最后一步只有两种来源:从上方 (i-1, j) 向下,或从左方 (i, j-1) 向右。因此普通位置满足:
这个定义把整条路径的枚举问题压缩成了局部累加。每个格子只关心两个已经计算好的前驱,而不必保存具体走法。

障碍物如何改变递推
障碍物不能被进入,所以对应状态直接设为 0。这条规则会自然阻断经过该位置的所有路径,无须额外记录“某条路线是否曾碰到障碍”。
最容易出错的是起点和边界。可以先令 dp[0][0] = 1,再统一扫描网格;遇到障碍立即写 0,其余格子分别累加存在的上方和左方状态。这样首行没有上方来源、首列没有左方来源,也不需要单独写复杂初始化逻辑。
用一次扫描完成计算
下面的程序使用 0 表示可通行格,1 表示障碍物。状态依赖只指向上方和左方,因此按行从左到右扫描时,读取到的前驱一定已经计算完成。
def count_paths(grid):
rows = len(grid)
cols = len(grid[0])
if grid[0][0] == 1 or grid[rows - 1][cols - 1] == 1:
return 0
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = 1
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
dp[i][j] = 0
continue
if i > 0:
dp[i][j] += dp[i - 1][j]
if j > 0:
dp[i][j] += dp[i][j - 1]
return dp[-1][-1]
grid = [
[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 0],
]
print(count_paths(grid))预期输出
4结果表示从左上角走到右下角共有 4 条不会经过障碍物的合法路径。
遍历顺序由依赖方向决定
动态规划的遍历顺序不能凭习惯选择,而要保证计算当前状态时,其依赖状态已经得到最终值。本题的依赖来自上方和左方,所以从上到下、从左到右最自然;若题目允许从下方或右方转移,遍历方向也要随之调整,甚至可能需要多轮计算或重新设计状态。
二维表需要 O(mn) 时间和 O(mn) 空间。由于第 i 行只依赖当前行左侧以及上一行同列,空间还能压缩成长度为 n 的一维数组,达到 O(n)。不过在刚学习网格状态建模时,先保留二维表通常更容易检查障碍物、边界和状态来源。