专题进阶 · 动态规划推荐总顺序 · 第 65 / 148 课

用二维坐标表示依赖,推导带障碍网格路径计数及滚动数组。

先学会这些,再进入本课 DP 思想 数组
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 动态规划

二维 DP2D DP

两个维度记录足够信息,如网格坐标或两个字符串的前缀长度。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用二维坐标表示依赖,推导带障碍网格路径计数及滚动数组。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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. 起点路径数为 1,障碍为 0,满足基础条件。
  2. 每条到当前格的路径恰好来自上或左,二者互斥且穷尽。
  3. 扫描顺序确保这两个依赖已正确保存,归纳得到终点计数。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

起点被挡返回什么?

需要一点提示

第一轮会清零 dp[0]。

查看解析与答案

0,后续无法凭空产生路径。

练习 2 · 边界与辨析

一行网格中间被挡,终点还能到达吗?

需要一点提示

只有向右移动。

查看解析与答案

不能,障碍之后所有位置都为 0。

练习 3 · 变式与迁移

改成每格有代价,求最小路径和怎么办?

需要一点提示

计数合并换成最优选择。

查看解析与答案

dp[r][c]=cost[r][c]+min(上,左),不可达状态用正无穷,起点初始化为自身代价。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。