01 / 本课学习路线
本课学习路线
阅读与推演约 112 分钟，练习约 62 分钟，进阶练习另需约 25 分钟
02 / 学习目标与先修自测
学完本课你能做什么，以及开始前需要会什么
本课把五要素搬到二维：状态多一个下标，初始化从一格变成一行一列，转移的依赖从「前几格」变成「上方、左方、左上方」。
| 学完后能做的事 | 正文位置 | 检查方式 |
|---|---|---|
| 用一句话说清两道必做题的边界初始化各是什么、为什么 | 第 04、06 节 | 自查第 2 条 |
| 压缩后能标出转移时每个依赖是新值还是旧值 | 第 05 节 | 自查第 3 条、练习 5 |
| 说出公共子串与公共子序列在转移上的差别 | 第 07 节 | 自查第 4 条 |
| 二维版与滚动版输出比对一致 | 第 05、08 节 | 自查第 5 条、必做任务 1 |
| 写对带障碍的路径计数与带斜边的最短距离，通过 P3398、P3397 | 第 08 节 | 必做任务 1、2 |
先修自测：下面 5 题请先自己写答案，再展开对照。答不出的按括号里的位置补看再回来。本课假定你已完成前两课的一维动态规划。
展开先修自测答案
自测 1：变成 [[1, 0], [1, 0]]——两行是同一个列表的两个名字，改一行另一行跟着变。二维表要写 [[0] * n for _ in range(m)]，每行各自新建。
自测 2：m, n = map(int, input().split())，然后 grid = [list(map(int, input().split())) for _ in range(m)]。也可以一次读完全部整数再按 i * n + j 取，本课参考程序用后一种。
自测 3：2。min(min(a, b), c) 或直接 min(a, b, c)；P3397 的转移先取上、左两者最小，字符相同时再和左上比较。
自测 4：A[i-1]。1 基的 dp 下标与 0 基的字符串下标相差 1，与上一课相同。
自测 5：空串。text1[end:end] 长度为 0，P3440「不存在公共子串输出空串」不需要特判。
03 / 概念与术语
二维状态、边界行列、依赖方向、旧值与新值
二维动态规划的转移仍然只有一行，难点全在「这一格依赖哪几格、它们此刻是否已经算好」。
| 术语 | 含义 | 代码里的位置 |
|---|---|---|
| 二维状态 | dp[i][j] 由两个下标共同确定：行列坐标，或两个字符串各自用掉的字符数 | 注释第一行、[[0] * (n + 1) for _ in range(m + 1)] |
| 边界行列 | 第 0 行 / 第 0 列没有上方或左方，值直接由题意给出 | 双重循环之前的两个单层循环 |
| 依赖方向 | 转移读上方、左方、左上方——它们都在「更小的 i 或 j」上 | 决定遍历顺序：i 从小到大、j 从小到大 |
| 滚动数组 | 只保留一行：dp[j] 同时扮演「上一行的第 j 格」和「本行的第 j 格」 | dp = [1] * n + 内层 dp[j] += dp[j-1] |
| 旧值 / 新值 | 本行更新到第 j 格时，dp[j] 还是旧值（上一行），dp[j-1] 已是新值（本行） | 压缩前在纸上给每个依赖标一个字 |
| 答案位置 | 路径与距离在右下角；「以 i、j 结尾」类状态的答案是全表最大值 | print 那一行 / 另记一个最大值 |
补充学习（选学）公共子串与公共子序列：转移的区别约 5 分钟P3440 的状态为什么在字符不同时要归零
最长公共子串（要求连续）：dp[i][j] = 以 A[i]、B[j] 结尾的公共后缀长度；A[i] == B[j] 时 dp[i][j] = dp[i-1][j-1] + 1，否则归零。答案是全表最大值（和「以 i 结尾」类状态一样，答案不在最后一格）。
最长公共子序列（LCS，允许跳过字符）：dp[i][j] = 前缀 A[..i]、B[..j] 的最长公共子序列长度；字符不同时不归零，而是取 max(dp[i-1][j], dp[i][j-1])。P3440 要求连续子串，应使用以两个位置结尾的公共后缀长度作为状态；子序列的转移不适用。动手前先确认题目要求的是连续子串还是子序列。
补充学习（选学）什么时候必须压缩：估算内存占用约 4 分钟m = n = 10⁴ 的二维表有多大
m = n = 10⁴ 时，二维 int 表有 10⁸ 个格子：C++ 的 int 约需 400 MB；Python 列表里每格是一个 8 字节的引用，仅引用就约 800 MB，还不算整数对象本身，会超出常见的内存限制。滚动成一维后只剩 10⁴ 个格子。P3398 行列 ≤ 100，开满二维表没有问题；P3397 串长 < 10000，两串都接近上限时二维表放不下，本课的完整程序用滚动两行。先在小输入上写对二维版，再按题目上限估算内存，决定是否压缩。
04 / 网格计数
dp[i][j] 来自上方与左方；障碍格为 0 且不向后传递
P3398「园区参观路径」：第一行是园区的行数和列数（1 ≤ 行、列 ≤ 100），接下来每行给出该行各格能否参观，0 可以、1 不可以；只能向右或向下走，输出从左上角到右下角的不同路径数。题面没有给示例，下面两张表是本课自己算的。
| j=0 | j=1 | j=2 | |
|---|---|---|---|
| i=0 | 1 | 1 | 1 |
| i=1 | 1 | 2 | 3 |
| i=2 | 1 | 3 | 6 |
答案 dp[2][2] = 6。每一格都是上格与左格之和：dp[1][2] = 1 + 2 = 3，dp[2][2] = 3 + 3 = 6。第 0 行与第 0 列没有上方或左方，缺项按 0 计，于是沿边界全是 1。
| j=0 | j=1 | j=2 | |
|---|---|---|---|
| i=0 | 1 | 1 | 1 |
| i=1 | 1 | 0（障碍） | 0 + 1 = 1 |
| i=2 | 1 | 1 + 0 = 1 | 1 + 1 = 2 |
障碍格的路径数是 0，而且它右边的格子只能从上方来（1 + 0），下边的格子只能从左方来（1 + 0）。答案 2：绕上边走或绕左边走。若障碍在第 0 行或第 0 列，它之后的边界格也都变成 0——「缺项按 0 计」的写法自动处理，不需要像参考题解那样在初始化里 break。
五要素：① dp[i][j] = 从左上角走到 (i, j) 的路径数；② dp[i][j] = 上方 + 左方，障碍格直接 0；③ dp[0][0] = 1（起点本身可参观时）；④ i 从上到下、j 从左到右；⑤ dp[m-1][n-1]。
05 / 滚动数组
只保留一行：更新到第 j 格时，dp[j] 是旧值、dp[j-1] 是新值
转移只读上方与左方，所以整张表可以压成一行：dp[j] 先扮演上一行的第 j 格，更新后变成本行的第 j 格。
3×3 全通：一维滚动三轮，与二维表逐行对照
初始（第 0 行） dp = [1, 1, 1] 第 1 行后 dp = [1, 2, 3] ← dp[j] += dp[j-1]，j 从左往右 第 2 行后 dp = [1, 3, 6] ✓ 与二维表最后一行相同 方向的含义：j 从左往右时，dp[j] 右侧仍是上一行（旧值），左侧已是本行（新值） 若某个转移需要「本行左侧的旧值」，从左往右就错了——压缩前先给每个依赖标出新值或旧值
3×3 中间有障碍：滚动时障碍格置 0
第 0 行后 dp = [1, 1, 1] 第 1 行后 dp = [1, 0, 1] ← (1,1) 是障碍，dp[1] 置 0；dp[2] = 旧值 1 + 新值 0 = 1 第 2 行后 dp = [1, 1, 2] ← dp[1] = 旧值 0 + 新值 1；dp[2] = 旧值 1 + 新值 1 = 2 ✓ 障碍格必须写成 dp[j] = 0，不能跳过不管：跳过会把上一行的旧值留在这一格，等于穿墙
一维滚动数组中新旧值的更新顺序
本课的路径计数需要「左方新值、上方旧值」，和正序更新相容；把 j 写成从右往左，dp[j-1] 读到的就是旧值，3×3 全通会得到 [1, 3, 4]、输出 4。下一课「0/1 背包与容量遍历顺序」的背包转移需要的全部是旧值，正序会读到本轮新值，等价于同一件物品被重复选取。两类问题的更新方向都由转移依赖决定，下一课会把两者对照比较。
从空文件写模板：滚动数组版路径计数
Python# 请补全以下网格动态规划练习模板，并标注更新前后的数组含义
import sys
def solve() -> None:
data = sys.stdin.read().split()
m, n = int(data[0]), int(data[1])
dp = [1] * n # 第 0 行：全 1（本模板先不管障碍；带障碍版见第 10 节练习 5）
for _ in range(1, m):
for j in range(1, n):
pass # 待完成：写出滚动转移——写之前先在纸上标出 dp[j]（旧值或新值）与 dp[j-1]（旧值或新值）
print(dp[n - 1])
solve()如果改求「最小路径和」，初始化不再是全 1：第 0 行和第 0 列要分别做前缀累加（第 10 节练习 2）。边界初始值由状态定义和题目要求决定，不是固定模板。
06 / 两个字符串的对齐
P3397：坐标是「各用掉几个字符」，边界是 i 和 j，斜边只在字符相同时可走
P3397「两个字符串间的最短路径」：一行空格分隔的两个大写字母串 A、B（长度 < 10000）。把 A 的字符排成列、B 的字符排成行，原点 (0, 0)、终点 (|A|, |B|)；每条水平边、垂直边距离 1；A 的第 i 个字符与 B 的第 j 个字符相同时，(i-1, j-1) 到 (i, j) 有一条距离也是 1 的斜边。输出原点到终点的最短距离。题面示例：ABCABBA CBABAC → 9。
| j=0 | C(1) | B(2) | A(3) | B(4) | A(5) | C(6) | |
|---|---|---|---|---|---|---|---|
| i=0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| A(1) | 1 | 2 | 3 | 3 | 4 | 5 | 6 |
| B(2) | 2 | 3 | 3 | 4 | 4 | 5 | 6 |
| C(3) | 3 | 3 | 4 | 5 | 5 | 6 | 6 |
| A(4) | 4 | 4 | 5 | 5 | 6 | 6 | 7 |
| B(5) | 5 | 5 | 5 | 6 | 6 | 7 | 8 |
| B(6) | 6 | 6 | 6 | 7 | 7 | 8 | 9 |
| A(7) | 7 | 7 | 7 | 7 | 8 | 8 | 9 ← 答案 |
验证三格：d[1][3]：A 与 B 的第 3 个字符 A 相同，可走斜边，min(d[0][3] = 3, d[1][2] = 3, d[0][2] = 2) + 1 = 3；d[3][1]：C 与 C 相同，min(3, 3, d[2][0] = 2) + 1 = 3；d[7][6]：A 与 C 不同，只能 min(d[6][6] = 9, d[7][5] = 8) + 1 = 9。每条边都是 1，所以「+ 1」放在 min 外面。
五要素：① d[i][j] = 从原点走到 (i, j) 的最短距离；② 上方、左方各 + 1，字符相同时左上方也 + 1，三者取最小；③ d[i][0] = i、d[0][j] = j（沿边只有直走）；④ i、j 都从小到大；⑤ d[|A|][|B|]。与编辑距离（模块 4 · 第 5 课）有两处区别：那里字符相同时走对角不加操作次数，这里斜边也算距离 1；那里字符不同时也有一条代价 1 的对角边（替换），这里字符不同就没有斜边。例如 A 与 B：本题距离 2，编辑距离 1。把本题的斜边代价改成 0，示例输出变成 5，正好是「只允许插入和删除」的距离（第 10 节练习 3）。
07 / 答案不在最后一格
P3440：以 (i, j) 结尾的公共后缀长度，字符不同归零，答案取全表最大值
P3440「寻找重复代码」：两行输入分别是两段代码 text1、text2（长度 ≤ 100，含字母、数字、空格），输出任一最长公共子串（要求连续）；不存在时输出空串。
| a | b | f | d | e | |
|---|---|---|---|---|---|
| a | 1 | 0 | 0 | 0 | 0 |
| b | 0 | 2 | 0 | 0 | 0 |
| c | 0 | 0 | 0 | 0 | 0 |
| d | 0 | 0 | 0 | 1 | 0 |
| e | 0 | 0 | 0 | 0 | 2 |
全表最大值 2 出现两次：(b, b) 对应 "ab"，(e, e) 对应 "de"；两者都是合法答案，参考程序用「严格大于才更新」保留最先出现的 "ab"。右下角 dp[5][5] = 2 只是碰巧：换成 abcxyz 与 xabcq，答案 abc 在表中间，右下角是 0。
记录长度的同时记录它在 text1 里的结尾位置 end，答案就是 text1[end - best:end]。输入是两行，代码里含空格，必须按行读（readline），不能用 split() 一次拆开。
08 / 从二维表到程序
三道题的完整参考程序，每一步落在哪几行
先自己写完并提交一次，再展开对照。
| 要素 | P3398 | P3397 | P3440 |
|---|---|---|---|
| ① 状态 | dp[i][j] 到 (i, j) 的路径数 | d[i][j] 各用掉 i、j 个字符时的最短距离（只保留 prev / cur 两行） | dp[i][j] 以 i、j 结尾的公共后缀长度 |
| ② 转移 | 上 + 左；障碍 0 | min(上, 左, 相同时左上) + 1 | 相同：左上 + 1；不同：0 |
| ③ 初始化 | dp[0][0] = 1，缺项按 0 | prev = 0..m（第 0 行 d[0][j] = j）、每行 cur[0] = i（第 0 列 d[i][0] = i） | 全 0 |
| ④ 遍历顺序 | i、j 从小到大 | 同左 | 同左 |
| ⑤ 答案位置 | dp[m-1][n-1] | prev[m]（即 d[n][m]） | 另记最大值 best 与结尾 end |
展开完整参考程序 1：P3398 园区参观路径（先自己写完并提交一次，再展开对照）
完整程序：P3398（标准输入 → 标准输出）
Pythonimport sys
data = sys.stdin.read().split()
m, n = int(data[0]), int(data[1]) # 行数、列数
grid = [[int(data[2 + i * n + j]) for j in range(n)] for i in range(m)]
dp = [[0] * n for _ in range(m)] # ① dp[i][j] = 从左上角走到 (i, j) 的路径数
dp[0][0] = 1 if grid[0][0] == 0 else 0 # ③ 起点本身
for i in range(m): # ④ 逐行、行内逐列
for j in range(n):
if grid[i][j] == 1: # 不能参观的格子：路径数 0，并且不再向右、向下传递
dp[i][j] = 0
continue
if i == 0 and j == 0:
continue
up = dp[i - 1][j] if i >= 1 else 0 # ② 来自上方（第 0 行没有上方，按 0 计）
left = dp[i][j - 1] if j >= 1 else 0 # 来自左方（第 0 列没有左方，按 0 计）
dp[i][j] = up + left
print(dp[m - 1][n - 1]) # ⑤ 右下角自测建议：第 04 节两张表（6、2）、练习 1（4）、起点被围死（0）、终点不能参观（0）。一次读完全部整数再按 i * n + j 取，输入分几行都不影响。
展开完整参考程序 2：P3397 两个字符串间的最短路径
完整程序：P3397（标准输入 → 标准输出）
Pythonimport sys
a, b = sys.stdin.readline().split()
n, m = len(a), len(b)
# ① d[i][j] = 从原点走到「A 用掉 i 个字符、B 用掉 j 个字符」这一格的最短距离；只保留上一行 prev 和本行 cur
prev = list(range(m + 1)) # ③ 第 0 行 d[0][j] = j：只走水平边
for i in range(1, n + 1): # ④ 逐行
cur = [i] + [0] * m # ③ 第 0 列 d[i][0] = i：只走垂直边
ai = a[i - 1]
for j in range(1, m + 1): # 行内逐列
best = prev[j] if prev[j] < cur[j - 1] else cur[j - 1] # ② 上方或左方，各走一条边
if ai == b[j - 1] and prev[j - 1] < best: # 字符相同才有斜边，斜边也算 1
best = prev[j - 1]
cur[j] = best + 1
prev = cur
print(prev[m]) # ⑤ 终点 d[n][m]只保留两行：prev 是上一行、cur 是本行，空间为 O(|B|)。时间仍是 O(|A|·|B|)：两串都接近上限 10⁴ 时约 10⁸ 次转移。滚动数组减少的是内存，不会减少填表次数；提交前要结合所用语言及题目的时间限制评估运行时间。自测建议：题面示例（9）、AB AB（2）、A B（2）、ABCD BC（4）；想进一步验证，可与第 06 节的二维表写法对拍随机短串。
展开完整参考程序 3：P3440 寻找重复代码（进阶练习）
完整程序：P3440（标准输入 → 标准输出）
Pythonimport sys
text1 = sys.stdin.readline().rstrip("\n")
text2 = sys.stdin.readline().rstrip("\n")
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)] # ① dp[i][j] = 以 text1 第 i 个、text2 第 j 个字符结尾的公共后缀长度
best, end = 0, 0 # 答案不在最后一格：另记全表最大值和它在 text1 里的结尾位置
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1 # ② 相同：接在左上角后面
if dp[i][j] > best: # 严格大于：长度相同时保留最先找到的
best, end = dp[i][j], i
# 不同：保持 0（列表初始化已是 0）
print(text1[end - best:end]) # ⑤ 长度 0 时切片为空串自测建议：第 07 节的 abcde / abfde（ab）、abcxyz / xabcq（abc）、含空格的两行 int a = 1; / int b = 1;（ = 1;）、无公共子串（空行）。长度相同时保留最先出现的，与题目页参考题解一致。
09 / 边界、反例与复杂度
错误做法在具体输入上各输出什么
下面每一行都是一个具体的错误程序，给出输入、错误输出与正确输出；把参考程序改成对应写法就能复现。
| 错误做法 | 输入 | 错误输出 | 正确输出 | 判题结果 |
|---|---|---|---|---|
| P3398 障碍格不置 0、照常累加 | 3×3，(1,1) 障碍 | 6 | 2 | 答案错误（WA） |
| P3398 二维表建成 n 行 m 列（行列写反） | 3 行 4 列 | 抛出 IndexError | 4 | 运行错误（RE） |
| P3398 滚动数组 j 从右往左 | 3×3 全通 | 4 | 6 | 答案错误（WA） |
| P3397 边界不初始化（全 0） | 题面示例 | 6 | 9 | 答案错误（WA） |
| P3397 斜边不判断字符是否相同 | 题面示例 | 7 | 9 | 答案错误（WA） |
| P3397 斜边代价写成 0（编辑距离的写法） | 题面示例 | 5 | 9 | 答案错误（WA） |
| P3440 字符不同时取 max(上, 左)（子序列的转移） | abcde / abfde | bcde | ab | 答案错误（WA） |
| P3440 答案取右下角 | abcxyz / xabcq | 空串 | abc | 答案错误（WA） |
| P3440 两行按空格一次拆开 | int a = 1; / int b = 1; | 抛出 ValueError | = 1; | 运行错误（RE） |
第一行的 6 就是「穿墙」：障碍格保留了上一行的旧值。第七行的 bcde：子序列的转移算出的是最长公共子序列的长度 4，再按这个长度去切 text1 就得到 bcde——它既不是连续子串，也不是两串的公共子序列（abfde 里没有 c）；一个真正的最长公共子序列是 abde，而题目要的连续子串是 ab。
| 做法 | 时间 | 空间 | 本课规模下 |
|---|---|---|---|
| 二维表 | O(mn) | O(mn) | P3398 100×100、P3440 串长 ≤ 100 都很小；P3397 两串接近 10⁴ 时约 10⁸ 格，Python 放不下 |
| 滚动一行 / 两行 | O(mn) | O(n) | 内存只与一行同阶；P3397 的完整程序用两行滚动，时间仍是 O(mn) |
| 枚举所有路径 / 所有子串 | 指数级 / O(m²n) | 递归深度 m + n | 10×10 网格 48620 条路径，20×20 约 3.5×10¹⁰ 条，超时 |
10 / 渐进练习与参考答案
跟做 → 改一个条件 → 独立实现 → 迁移
每题先在纸上或文件里做完，再展开答案。
练习 1（跟做）：3 行 4 列，(1, 1) 不能参观，按第 04 节表的格式填出全表，写出右下角的值。
展开练习 1 答案
第 0 行：1 1 1 1；第 1 行：1 0 1 2；第 2 行：1 1 2 4。答案 4。做错最常见的原因：(1, 2) 忘了只能从上方来（0 + 1 = 1）。
练习 2（改一个条件）：把「路径数」改成「路径上数字之和的最小值」，网格 1 3 1 / 1 5 1 / 4 2 1。五要素哪几条变了？答案是多少？
展开练习 2 答案
转移变成 min(上, 左) + 本格；初始化变成前缀累加：第 0 行 1 4 5、第 0 列 1 2 6。全表：1 4 5 / 2 7 6 / 6 8 7，答案 7（1→3→1→1→1）。状态含义从「到 (i, j) 的路径数」变成「到 (i, j) 的最小累计和」；坐标维度、遍历顺序、答案位置不变。
练习 3（改一个条件）：P3397 的斜边代价改成 0，题面示例的输出变成多少？这个数和两个串的最长公共子序列有什么关系？
展开练习 3 答案
5。斜边不花代价时，最优走法是尽量多走斜边：走 k 条斜边就少走 2k 条直边，总距离 = |A| + |B| − 2k，k 最大就是最长公共子序列长度 4，所以 7 + 6 − 8 = 5。这也是编辑距离课里「只允许插入和删除」的距离。
练习 4（独立实现）：完成「代码自测」的 grid_paths_rolled，再加两条断言：3 行 4 列 → 10，4 行 4 列 → 20。
展开练习 4 答案
grid_paths_rolled 的参考实现（自带断言）
Pythondef grid_paths_rolled(m: int, n: int) -> int:
dp = [1] * n # 第 0 行：沿上边界只有一条走法
for _ in range(1, m): # 再推 m-1 行
for j in range(1, n): # j 从左往右
dp[j] += dp[j - 1] # dp[j] 是上一行的旧值，dp[j-1] 已是本行的新值
return dp[n - 1]
assert grid_paths_rolled(3, 3) == 6
assert grid_paths_rolled(1, 5) == 1 # 单行只有一条
assert grid_paths_rolled(2, 2) == 2
assert grid_paths_rolled(3, 4) == 10 # 与二维表 dp[2][3] 对照
assert grid_paths_rolled(4, 4) == 20内层 j 从 1 开始：第 0 列永远是 1，不需要更新。
练习 5（迁移）：把带障碍的 P3398 也写成滚动数组：障碍格怎么处理？用第 04 节的两张表和练习 1 验证。
展开练习 5 答案
带障碍的滚动数组版路径计数（自带断言）
Pythondef grid_paths_obstacle(grid):
m, n = len(grid), len(grid[0])
dp = [0] * n
dp[0] = 1 if grid[0][0] == 0 else 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
dp[j] = 0 # 障碍：本行这一格置 0，上一行的旧值不能再用
elif j >= 1:
dp[j] += dp[j - 1] # dp[j] 是上一行的旧值，dp[j-1] 是本行的新值
return dp[n - 1]
assert grid_paths_obstacle([[0, 0, 0], [0, 0, 0], [0, 0, 0]]) == 6
assert grid_paths_obstacle([[0, 0, 0], [0, 1, 0], [0, 0, 0]]) == 2 # 第 04 节表
assert grid_paths_obstacle([[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0]]) == 4
assert grid_paths_obstacle([[0, 1], [1, 0]]) == 0 # 起点被围死
assert grid_paths_obstacle([[0, 0, 0], [0, 0, 0], [0, 0, 1]]) == 0 # 终点不能参观障碍格写 dp[j] = 0，把上一行留在这一格的旧值清掉；第 0 列的障碍同样由这一行处理，所以不需要单独初始化第 0 列。
11 / 读题要求与复习自评
三道题的要求对照，以及完成本课之后怎么复习
提交前把下表过一遍；题目页的题面与样例是最终依据。
| 项目 | P3398 园区参观路径 | P3397 两串最短路径 | P3440 寻找重复代码 |
|---|---|---|---|
| 输入 | 第一行行数、列数；再每行 0/1 | 一行两个大写字母串，空格分隔 | 两行，各一段代码（含空格） |
| 输出 | 路径数 | 最短距离 | 任一最长公共子串；无则空串 |
| 状态 | 到 (i, j) 的路径数 | 各用掉 i、j 个字符时的最短距离 | 以 i、j 结尾的公共后缀长度 |
| 边界 | 缺项按 0，障碍 0 | d[i][0] = i、d[0][j] = j | 全 0 |
| 答案位置 | 右下角 | 右下角 | 全表最大值 |
| 示例 | 3×3 全通 → 6（本课自算） | ABCABBA CBABAC → 9 | abcde / abfde → ab（本课自算） |
需要对照解法时，展开本课第 08 节的完整参考程序；题目页另有思路与参考代码，可在题目页查看。完成条件：本课算完成 = P3398、P3397 两道必做题都通过判题，并勾选全部六条「学习完成检查」；六条检查是自评，勾选不改变题目的通过（AC）状态；进阶练习与复习题单独统计，不影响完成状态。复习时用三个问题自测：① 不看正文，说出三道题各自的边界初始化；② 不看表格，把 3×3 中间有障碍的网格滚动三轮；③ 说出斜边代价 1 和 0 的两种题各对应什么。答不出哪一条，就回到对应的节重读，再做第 10 节对应的练习。
12 / 练习
按顺序完成本课的任务
必做题已通过 0/2 道；进阶练习已通过 0/1 道
滚动数组版路径计数（grid_paths_rolled）
代码自测自主练习练习重点：一维滚动写法，用 3×3 = 6 验证；预计用时：12 分钟
完成标准：能说出转移时 dp[j] 与 dp[j-1] 各是哪一行的值
需要时查看提示
初始 dp = [1]*n；外层循环 m-1 轮，内层 j 从 1 到 n-1 执行 dp[j] += dp[j-1]。断言里的单行网格用于检查边界。参考实现在第 10 节练习 4 的展开区。
自测代码（复制到你的代码文件中运行，检查输出是否一致）
def grid_paths_rolled(m: int, n: int) -> int:
# 你来写：m×n 网格从左上到右下的路径数，用一维滚动
...
assert grid_paths_rolled(3, 3) == 6
assert grid_paths_rolled(1, 5) == 1 # 单行只有一条
assert grid_paths_rolled(2, 2) == 2
# 通过后再自问：滚动转移里 dp[j] 和 dp[j-1] 此刻各是哪一行的值？P3398 · 园区参观路径
必做任务 1练习重点：二维版先通过，再换滚动数组版重新提交；预计用时：20 分钟
完成标准：两个版本都通过判题，且能用一句话说清边界初始化和障碍处理
需要时查看提示
先读行数、列数，再读 0/1 网格；1 表示不能参观。障碍格路径数为 0 且不向右、向下传递。路径数按组合数增长：100×100 全通时是 C(198,99)，十进制有 59 位，二进制有 194 位，64 位整数放不下（35×35 就已超过）。Python 整数支持大整数；Java 可用大整数类（BigInteger），C++ 可用大整数库或实现大整数加法。题目没有要求取模时，不能自行取模。第 04 节有两张逐格表。
P3397 · 两个字符串间的最短路径
必做任务 2练习重点：斜边条件、1 基边界初始化（d[i][0]=i、d[0][j]=j）；预计用时：30 分钟
完成标准：能解释斜边为什么只在字符相同时可走、边界为什么是 i 和 j
需要时查看提示
转移取三者最小：上方 d[i-1][j]+1、左方 d[i][j-1]+1、（A[i-1]==B[j-1] 时）斜向 d[i-1][j-1]+1。本题斜边也算距离 1，与编辑距离「相同不加操作」不同，请按本题题目要求计算。第 06 节有完整距离表。
P3440 · 寻找重复代码（最长公共子串）
进阶练习 1进阶练习练习重点：「以 i、j 结尾」状态 + 字符不同时归零，答案取全表最大值；预计用时：25 分钟
完成标准：能说出子串和子序列在转移上的那一处不同
需要时查看提示
记录最大长度的同时记录结尾位置，才能还原子串本身；没有公共子串时输出空串。输入是两行、代码里含空格，按行读。串长 ≤ 100，O(mn) 可以通过。第 07 节有 5×5 表。
提交结果
提交结果说明与处理方法
- WA
答案错误
优先检查三处：边界行列初始化遗漏（表全 0）、障碍格没置 0（穿墙）、滚动方向错误（对照二维版逐行打印比对）。第 09 节的表给出了每种错误的具体输出。
- RE
运行错误
二维表下标 [i][j] 与 [j][i] 写反，在非方阵上会越界；m、n 的读入顺序要和题目要求核对；P3440 要按行读。
- TLE
超时
本课的规模下 O(mn) 都能通过；超时先检查是否在内层循环里重复创建列表。
- MLE
内存超限
开满二维表仍超限时，按补充学习里的方法估算内存，改用滚动数组。
- AC
通过
把二维版和滚动版在多组已知期望值的用例上逐行比对，并检查每个状态依赖的更新时序。
13 / 学习完成检查
本课学习完成检查
完成本课需要：必做题全部通过，并勾选本课的全部学习完成检查；进阶练习、基础加练与复习题单独统计，不影响完成状态。登录后，勾选记录会保存到账号，并更新课程总览的完成状态。