01先把问题说具体
从网格左上走到右下,每次只能向右或向下,障碍格不可进入。怎样计算不同路径数?
02一步步得到方法
状态是到达一个格子的全部走法
dp[r][c] 表示从起点到 (r,c) 的合法路径数。最后一步只能来自上方或左方,两类路径的最后边不同,所以计数相加;障碍格必须为 0。
起点无障碍时置 1,表示长度为零的初始路径。不要把整条首行首列无条件填 1,因为遇到障碍后后续格子可能不可达。
压缩一维时同一数组中有两种时间
按行从左到右扫描:更新前 dp[c] 保存上一行同列结果,已更新的 dp[c−1] 保存当前行左侧结果。两者相加正好是上方加左方。
遇障碍时必须把 dp[c] 清零,否则上一行的路径数会穿过障碍残留下来。空间压缩不是机械地删除一维,而是重新解释更新前后每个槽位的含义。
两条坐标轴各自代表什么
二维状态不是为了把表画得更大,而是结果同时依赖两个独立进度。例如网格路径取行列坐标,字符串问题取两个前缀长度,背包取物品数与容量。
计算顺序必须使依赖先于当前状态完成。网格只从上和左来时可以按行推进;若出现从右或未来行来的依赖,就不能未经分析照搬相同双循环。
03把一个小例子完全算清楚
3×3 网格,中心 (1,1) 为障碍。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 第一行 | [1,1,1] | 只可一直向右 |
| 第二行 | [1,0,1] | 中心清零 |
| 第三行 | [1,1,2] | 右下由上方 1 加左方 1 |
窄屏可左右滑动表格,阅读完整计算与理由。
答案 2:沿上边再向下,或沿左边再向右。
04为什么这个方法成立
- 起点路径数为 1,障碍为 0,满足基础条件。
- 每条到当前格的路径恰好来自上或左,二者互斥且穷尽。
- 扫描顺序确保这两个依赖已正确保存,归纳得到终点计数。
05把推导翻译成代码
Python · 可独立运行的教学实现
def grid_paths(blocked):
if not blocked or not blocked[0]:
return 0
cols = len(blocked[0])
dp = [0]*cols
dp[0] = 1
for row in blocked:
for c in range(cols):
if row[c]:
dp[c] = 0
elif c > 0:
dp[c] += dp[c-1]
return dp[-1]逐个理解关键决定
dp[c] = 0- 障碍切断所有通过该格的路径,不能保留旧值。
dp[c] += dp[c-1]- 更新前是上方,左边已经是本行;顺序就是算法的一部分。
06时间、空间与实现范围
R×C 个状态,时间 O(RC),滚动空间 O(C)。
路径数可能非常大,若题目要求取模需每次加法后取模;本 Python 版使用任意精度整数。
07改变条件,检查哪里会出错
把每一格初始化为 1
内部格子的路径数不是基础值,应由依赖推导。
对所有二维 DP 使用同一遍历方向
应依据状态依赖图决定方向;二维数组的形状本身不提供正确计算顺序。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
起点被挡返回什么?
需要一点提示
第一轮会清零 dp[0]。
查看解析与答案
0,后续无法凭空产生路径。
一行网格中间被挡,终点还能到达吗?
需要一点提示
只有向右移动。
查看解析与答案
不能,障碍之后所有位置都为 0。
改成每格有代价,求最小路径和怎么办?
需要一点提示
计数合并换成最优选择。
查看解析与答案
dp[r][c]=cost[r][c]+min(上,左),不可达状态用正无穷,起点初始化为自身代价。