01 / 本课学习路线
本课学习路线
阅读与推演约 108 分钟，练习约 70 分钟
02 / 学习目标与先修自测
学完本课你能做什么，以及开始前需要会什么
本课在上一课五要素之上加两件事：转移前先判断合法，计数结果逐步取模。
| 学完后能做的事 | 正文位置 | 检查方式 |
|---|---|---|
| 说出 0 的三条规则，并指出各自在代码里的拦截位置 | 第 04 节 | 自查第 2 条、必做任务 1 |
| 解释为什么每步取模而不是最后取一次 | 第 06 节 | 自查第 3 条 |
| 跳格子的 0 基与 1 基两种写法都能独立完成 | 第 07 节 | 自查第 4 条、练习 5 |
| 说出哨兵位 dp[0] 的含义和它减少了哪些边界判断 | 第 07 节 | 自查第 5 条 |
| 写出带合法性判断和取模的计数型动态规划，通过 AI019 | 第 05、08 节 | 必做任务 1 |
先修自测：下面 5 题请先自己写答案，再展开对照。答不出的按括号里的位置补看再回来。本课假定你已完成上一课「动态规划基础」。
展开先修自测答案
自测 1：s[i-1]。1 基的 dp 下标与 0 基的字符串下标相差 1，本课程序里所有 s[i-1]、s[i-2] 都由此而来。
自测 2：6。所以只写「≤ 26」拦不住 06，两位成码必须同时判断下界 10——第 04 节的 ok2。
自测 3：相同。加法可以逐步取模，这是「每步取模」正确的依据；本课没有减法与除法。
自测 4：第 i-1 个与第 i 个字符（0 基下标 i-2、i-1）。i = 2 时是 s[0:2]，即前两个字符。
自测 5：走到第 0 级（原地不动）算一种方法。本课 dp[0] = 1 的含义是「空串有一种还原方式」，作用相同：让第一格能从它转移。
03 / 概念与术语
合法转移、哨兵位、逐步取模、滚动变量
线性动态规划的状态沿一条线（字符串或数组的前缀）推进。本课新增的四个词都和「转移那一行」有关。
| 术语 | 含义 | 代码里的位置 |
|---|---|---|
| 前缀状态 | dp[i] 只描述前 i 个字符 / 格子，后面的不参与 | 注释第一行、数组长度 n + 1 |
| 合法转移 | 一条来源只有在题目规则允许时才能加进来 | if ok1(...)、if ok2(...) 两行 |
| 哨兵位 | dp[0] 表示空前缀，值由题意定（计数题 1、最大值题 0） | 循环之前那一行 |
| 逐步取模 | 每次加法之后立刻对 10⁹ + 7 取余，而不是最后一次 | 转移那一行末尾的 % MOD |
| 滚动变量 | 转移只读前两格时，用两个变量代替整条数组 | 见「补充学习」与必做任务 1 的提示 |
补充学习（选学）取模规则：为什么不能等到最后约 4 分钟长度 10 万的串，方案数有多大
解码方案数按斐波那契数列的速度增长：长度 45 的全部可双解的串，方案数为 1,836,311,903（第 46 个斐波那契数），还没有超过 2^31=2,147,483,648；长度 46 时方案数 2,971,215,073 首次超过 2^31。长度 10 万时远超常用整数类型的范围：Python 大整数不会溢出，但大数加法会越来越慢；C++ 和 Java 不取模则直接溢出。因此每次转移后立刻对 10^9 + 7 取模。
AI019 题目还有一条易错点：中途取模后不要因为余数为 0 就提前退出。取模后的余数为 0，不等于真实方案数为 0。长度 10 万的串方案数有两万多位，某个前缀的真实方案数恰好是 10⁹ + 7 的倍数完全可能，此时余数为 0，但后面仍可能形成合法方案。规则是：合法性判断决定「能不能转移」，取模只负责控制数值范围，两者分别处理；无解由合法性自然算出（最终 dp[n] 的余数为 0 就按题目要求输出 0），不要手工提前返回。
补充学习（选学）序列解码在 AI 中的应用约 4 分钟标签还原、维特比解码、束搜索属于同一类问题
AI019 的场景（标注平台压缩标签序列）来自真实工作流：序列标注和语音识别的解码器都需要把一串数字或概率还原成合法序列。维特比（Viterbi）解码用 dp[i][s] 表示处理到第 i 个词、标记为状态 s 时的最优得分，可以看作本课转移的多状态版本。
大语言模型（LLM）逐个词元（token）生成时使用的束搜索（beam search）是另一个方向：候选路径数量可能指数增长，不适合保存全部路径，每步只保留得分最高的 k 条。完整的动态规划得到全局最优，束搜索得到近似解。模块 7 · 第 3 课「KV 缓存与束搜索」做 AI028 时会完整说明束搜索的实现。
补充学习（选学）零钱兑换：从最后一枚硬币写出转移约 5 分钟dp[i] = 凑出金额 i 的最少硬币数；不可达记为无穷大，最终输出 −1
手算：硬币面额（coins）= [1, 2, 5]、目标金额（amount）= 11
dp[0] = 0，其余先设无穷大（inf） dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3] 金额 11 的最后一枚: 取 1 → 看 dp[10]=2；取 2 → 看 dp[9]=3；取 5 → 看 dp[6]=2 dp[11] = min(2, 3, 2) + 1 = 3，对应 11 = 5 + 5 + 1
「最后一枚是哪种硬币」把大问题拆成几个更小的同型问题。转移写成更新式：对每枚满足 c ≤ i 且 dp[i−c] 可达的硬币，执行 dp[i] = min(dp[i], dp[i−c] + 1)；一枚合法硬币都没有时，dp[i] 保持无穷大。无穷大一路传下去就是「凑不出」：dp[amount] 仍是无穷大时输出 −1。硬币可以重复使用，所以 dp[i−c] 里允许再次出现同一面额——按金额从小到大填表，天然就是这个语义。基础题 H100016 练这一条；它与本课解码题的区别是 dp[i−c] 会回看任意远的格子，不能压成两个滚动变量。
补充学习（选学）最长递增子序列：从 O(n²) 到二分优化约 6 分钟dp[i] 以 i 结尾；最小结尾值数组（tails）+ 下界查找把 n² 降到 n·log₂ n
基线状态：dp[i] 是「以位置 i 结尾」的最长严格递增子序列长度；记输入数组为 nums，只从 j < i 且 nums[j] < nums[i] 的位置转移，相等不算严格递增；答案是全部 dp[i] 的最大值，不保证出现在最后一格。内层要扫全部 j < i，所以是 O(n²)——先把这一版写到通过，作为可核对的基线。
tails 数组 + 下界查找（lower_bound）
Pythonfrom bisect import bisect_left
def lis_length(nums):
tails = [] # tails[k] = 长度 k+1 的递增子序列的最小结尾值
for x in nums:
pos = bisect_left(tails, x) # 下界查找：第一个 >= x 的位置（严格递增，相等不能接）
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)
assert lis_length([10, 9, 2, 5, 3, 7, 101, 18]) == 4
assert lis_length([1, 1, 1]) == 1tails[k] 表示长度为 k + 1 的递增子序列可取得的最小结尾值。tails 天然有序，于是「x 能接到多长的序列后面」就变成在 tails 里找 x 的下界位置——模块 2 · 第 5 课 的二分模板原样搬来；每个元素一次二分，总时间 O(n log n)。
手算：[10, 9, 2, 5, 3, 7, 101, 18] 的最小结尾值数组（tails）演化
[10] → [9] → [2] → [2, 5] → [2, 3] → [2, 3, 7] → [2, 3, 7, 101] → [2, 3, 7, 18] 长度 4 就是答案；tails 本身不一定是一条真实子序列，它的长度才是答案
基础题 H100015 练这一条：两版用几组随机数据对拍，结果一致再提交二分版。
04 / 解码规则清单
0 的三条规则，落到两个判断函数上
AI019「标注序列还原计数」：一行数字串 s（1 ≤ |s| ≤ 100000，只含 0–9），每个标签的类别编号在 1..26 之间、按顺序拼接不加分隔符；输出能还原成多少种标签序列，对 1000000007 取模，无法还原输出 0。题面示例：12 → 2（1|2、12）；226 → 3。
| 规则 | 例子 | 拦截位置 |
|---|---|---|
| 0 不能单独成码 | "0" → 0；"100" → 0（10 之后的 0 无处安放） | ok1(c)：c != "0" |
| 两位数只有 10..26 合法 | "06" 不合法（下界）；"27" 只能 2|7（上界） | ok2(c1, c2)：10 <= int(c1 + c2) <= 26 |
| 首字符为 0 时无解 | "06" → 0 | 不需要单独写：第 1 个字符两条来源都不合法，dp[1] = 0 并一路传下去 |
把判断从转移方程里拆出来单独实现：先写单独成码判断（ok1）和两位成码判断（ok2）并用几个字符测通，再写转移。转移只有两行：第 i 个字符单独成码则加 dp[i-1]；第 i-1、i 两个字符成码则加 dp[i-2]。两条来源互斥（最后一个标签要么 1 位要么 2 位），所以相加不会重复计数。
05 / 填表推演
"226"、"12120" 逐位填表；无解如何自然算出
状态沿用 1 基哨兵写法：dp[i] = 前 i 个字符的还原方案数，dp[0] = 1。每一位有两条来源：单独成码（合法才加 dp[i-1]）、和前一位组成两位码（合法才加 dp[i-2]）。
| i | 字符 | 取 1 位（是否合法） | 取 2 位（是否合法） | dp[i] |
|---|---|---|---|---|
| 0 | — | — | — | 1 |
| 1 | 2 | "2" 合法 → +dp[0] | — | 1 |
| 2 | 2 | "2" 合法 → +dp[1] | "22" 合法 → +dp[0] | 2 |
| 3 | 6 | "6" 合法 → +dp[2] | "26" 合法 → +dp[1] | 3 |
dp[3] = 2 + 1 = 3：对应 2|2|6、22|6、2|26。
| i | 字符 | 取 1 位 | 取 2 位 | dp[i] |
|---|---|---|---|---|
| 0 | — | — | — | 1 |
| 1 | 1 | 合法 → +dp[0] = 1 | — | 1 |
| 2 | 2 | 合法 → +dp[1] = 1 | "12" 合法 → +dp[0] = 1 | 2 |
| 3 | 1 | 合法 → +dp[2] = 2 | "21" 合法 → +dp[1] = 1 | 3 |
| 4 | 2 | 合法 → +dp[3] = 3 | "12" 合法 → +dp[2] = 2 | 5 |
| 5 | 0 | "0" 不合法 → 0 | "20" 合法 → +dp[3] = 3 | 3 |
最后一位是 0 时只剩「和前一位组成 20」这一条来源，dp[5] = dp[3] = 3：1|2|1|20、12|1|20、1|21|20。程序输出同样是 3。
无解与「只有一条来源」由转移自然算出
"06": i=1 "0" 不合法 → dp[1]=0；i=2 "6" 合法 +dp[1]=0，"06" 不合法 → dp[2]=0 → 输出 0 "100": dp=[1,1,1,0]：i=3 "0" 不合法，"00" 不合法 → 0 → 输出 0 "2101": dp=[1,1,2,1,1]：i=2 "1" 合法 +dp[1]、"21" 合法 +dp[0] → 2；i=3 "0" 不合法、"10" 合法 +dp[1]=1 → 1；i=4 "1" 合法 +dp[3]=1、"01" 不合法 → 输出 1（只能 2|10|1） "27": dp=[1,1,1]："27" 不合法，只有 2|7 → 输出 1；"26": dp=[1,1,2] → 输出 2 不需要任何「提前返回」：无解就是最后一格为 0
从空文件写模板：哨兵位与两个合法性判断
Python# 请补全以下线性动态规划练习模板，并按题目要求核对合法区间和取模
import sys
def solve() -> None:
s = sys.stdin.readline().strip()
MOD = 10**9 + 7
n = len(s)
# 采用 1 基下标并设置哨兵：dp[0] = 1，表示空串有一种还原方式
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
# 待完成 1：取 1 位——先判合法（当前位是否非 0）
# 待完成 2：取 2 位——先判 i >= 2，再判两位组成的数在 10..26
# 待完成 3：每步取模，不要等到最后
pass
print(dp[n])
solve()合法区间的上下界（10..26）以题目要求为准逐字核对。把 06 当成合法、或把 27 算进来，这类错误可能不被示例覆盖，应增加包含 0 和上下界的测试用例，例如 06、100、27、26、2101、1001。
06 / 逐步取模
方案数有多大，为什么每一步都要取模
全 1 串的方案数就是斐波那契数："1111" → 5，长度 45 → 1,836,311,903，长度 46 首次超过 2³¹。长度 10 万的全 1 串是合法输入，参考程序输出 967618232（对 10⁹ + 7 取模后的值）。
| 写法 | Python | C++ / Java |
|---|---|---|
每步 dp[i] = (dp[i-1] + dp[i-2]) % MOD | 正确，数值始终 < 10⁹ + 7 | 正确，两数之和 < 2·10⁹，用 64 位相加更稳妥 |
最后 print(dp[n] % MOD) | 结果正确，但方案数会长到两万多位，大整数加法逐渐变慢 | 错误：中间值溢出，输出负数或错值 |
| 取模后遇 0 提前返回 | 错误：余数 0 ≠ 真实方案数 0 | 同左 |
本课的转移只有加法，所以逐步取模与最后取模在数学上等价（自测 3）；差别只在中间值的大小。
07 / 跳格子：两种下标写法
不选相邻格子的最大和；0 基与 1 基并排对照
P3403「跳格子」：一行空格分隔的非负整数（1 ≤ 长度 ≤ 100，0 ≤ 分数 ≤ 1000），可以从任意格子起跳、不能跳连续的格子、不能回头；输出最高分。题面示例：2 7 9 3 1 → 12（2 + 9 + 1）；1 2 3 1 → 4（1 + 3）。「任意起跳」和「不回头」都被「不选」分支覆盖，不需要额外处理。
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| a[i] | 2 | 7 | 9 | 3 | 1 |
| 不选 dp[i-1] | 0 | 2 | 7 | 11 | 11 |
| 选 dp[i-2]+a[i] | 0+2 | 0+7 | 2+9 | 7+3 | 11+1 |
| dp[i] | 2 | 7 | 11 | 11 | 12 |
dp[5] = max(11, 11 + 1) = 12：选下标 1、3、5（2 + 9 + 1）。i = 1 时「前面没有格子」按 0 计，这就是哨兵位 dp[0] = 0 的作用。
| 写法 | dp 表 | 初始化 | 答案位置 |
|---|---|---|---|
| 0 基：dp[i] = 下标 0..i 的最高分 | [1, 2, 4, 4] | dp[0] = a[0]，dp[1] = max(a[0], a[1])，n = 1 要特判 | dp[n-1] = dp[3] = 4 |
| 1 基：dp[i] = 前 i 个格子的最高分 | [0, 1, 2, 4, 4] | dp[0] = 0（空前缀哨兵） | dp[n] = dp[4] = 4 |
1 基写法多出 dp[0] = 0 作为「空前缀哨兵」，i-2 的缺项按 0 计，不需要特判 n = 1；两种写法答案位置不同，混用会取错格。题目页参考题解用 0 基并特判 n = 1，与这里等价。
为什么不能「隔一个取一个」：2 1 1 2 取奇数位得 3、取偶数位得 3，而最优是取首尾得 4。动态规划的「不选」分支允许连续跳过两个格子，贪心不允许。
08 / 从判断函数到程序
两道必做题的完整参考程序，每一步落在哪几行
先自己写完并提交一次，再展开对照。
| 要素 | AI019 | P3403 |
|---|---|---|
| ① 状态 | dp[i] 前 i 个字符的还原方案数 | dp[i] 前 i 个格子的最高分 |
| ② 转移 | if ok1(s[i-1]): dp[i] = dp[i-1]；if i >= 2 and ok2(...): dp[i] = (dp[i] + dp[i-2]) % MOD | dp[i] = max(dp[i-1], prev2 + a[i-1])，prev2 在 i = 1 时为 0 |
| ③ 初始化 | dp[0] = 1 | dp[0] = 0 |
| ④ 遍历顺序 | for i in range(1, n + 1) | 同左 |
| ⑤ 答案位置 | print(dp[n]) | print(dp[n]) |
展开完整参考程序 1：AI019 标注序列还原计数（先自己写完并提交一次，再展开对照）
完整程序：AI019（标准输入 → 标准输出）
Pythonimport sys
MOD = 10**9 + 7
def ok1(c: str) -> bool:
return c != "0" # 单独成码：只有 1..9 合法，0 不能单独成码
def ok2(c1: str, c2: str) -> bool:
return 10 <= int(c1 + c2) <= 26 # 两位成码：只有 10..26 合法（06、27 都不合法）
s = sys.stdin.readline().strip()
n = len(s)
dp = [0] * (n + 1) # ① 状态 dp[i] = 前 i 个字符的还原方案数
dp[0] = 1 # ③ 初始化：空串算一种（哨兵位）
for i in range(1, n + 1): # ④ 遍历顺序：从短前缀到长前缀
if ok1(s[i - 1]): # ② 转移来源 1：第 i 个字符单独成码
dp[i] = dp[i - 1]
if i >= 2 and ok2(s[i - 2], s[i - 1]): # 转移来源 2：第 i-1、i 两个字符成码
dp[i] = (dp[i] + dp[i - 2]) % MOD # 每步取模
print(dp[n]) # ⑤ 答案位置：整串自测建议：题面两组示例（2 / 3）、06、100、27、26、2101、1001，以及长度 10 万的全 1 串（967618232）。数组写法在 10 万长度下时间与空间都是 O(n)；要练滚动变量的，把 dp 换成两个变量再提交一次。
展开完整参考程序 2：P3403 跳格子
完整程序：P3403（标准输入 → 标准输出）
Pythonimport sys
a = [int(x) for x in sys.stdin.readline().split()]
n = len(a)
dp = [0] * (n + 1) # ① 状态 dp[i] = 只考虑前 i 个格子的最高分；③ dp[0] = 0 是空前缀哨兵
for i in range(1, n + 1): # ④ 从前往后
skip = dp[i - 1] # ② 不选第 i 个格子：分数与前 i-1 个相同
prev2 = dp[i - 2] if i >= 2 else 0 # 选第 i 个格子时，第 i-1 个必须不选；i = 1 时前面没有格子，按 0 计
take = prev2 + a[i - 1]
dp[i] = max(skip, take)
print(dp[n]) # ⑤ 答案位置：前 n 个格子自测建议：题面示例（12 / 4）、贪心反例 2 1 1 2（4）、单元素 5（5）。0 基写法见第 10 节练习 5 的展开区。
09 / 边界、反例与复杂度
错误做法在具体输入上各输出什么
下面每一行都是一个具体的错误程序，给出输入、错误输出与正确输出；把参考程序改成对应写法就能复现。
| 错误做法 | 输入 | 错误输出 | 正确输出 | 判题结果 |
|---|---|---|---|---|
| AI019 两位下界写成 0（只判 ≤ 26） | 06 | 1 | 0 | 答案错误（WA） |
| AI019 去掉单独成码判断（0 也算一码） | 100 | 2 | 0 | 答案错误（WA） |
| AI019 两位上界写成 27 | 27 | 2 | 1 | 答案错误（WA） |
| P3403 去掉「不选」分支（每格必选） | 2 1 1 2 | 3 | 4 | 答案错误（WA） |
| P3403 1 基写法答案取 dp[n-1] | 2 7 9 3 1 | 11 | 12 | 答案错误（WA） |
| P3403 0 基写法不特判 n = 1 | 5 | 抛出 IndexError | 5 | 运行错误（RE） |
| P3403 按逗号拆空格分隔行 | 2 7 9 3 1 | 抛出 ValueError | 12 | 运行错误（RE） |
第一行：06 这类前导零输入要专门测。第四行：每格必选时 2 1 1 2 只能得 2 + 1 = 3（第 3 格接在第 1 格后），而正确做法允许跳过第 2、3 格取首尾。
| 做法 | 时间 | 空间 | |s| = 10 万时 |
|---|---|---|---|
| 数组递推 | O(n) | O(n) | 10 万格，线性时间 |
| 两个滚动变量 | O(n) | O(1) | 同上，内存更省 |
| 递归枚举所有切分 | 指数级 | 递归深度 n | 超时且超过递归深度 |
10 / 渐进练习与参考答案
跟做 → 改一个条件 → 独立实现 → 迁移
每题先在纸上或文件里做完，再展开答案。
练习 1（跟做）：按第 05 节表的格式给 "1111" 填表，写出每一格的两条来源。
展开练习 1 答案
dp = [1, 1, 2, 3, 5]：每一位单独成码都合法，每两位 11 也合法，所以每格都是前两格之和，就是斐波那契数列。输出 5：1|1|1|1、11|1|1、1|11|1、1|1|11、11|11。
练习 2（改一个条件）：题目上界从 26 改成 29，代码要改哪一行？"29" 的输出变成多少？
展开练习 2 答案
只改 ok2 的上界：10 <= int(c1 + c2) <= 29。"29" 从 1（只有 2|9）变成 2（2|9、29）。转移、初始化、答案位置都不变。
练习 3（改一个条件）：P3403 改成「跳过的格子至少要隔两个」（选了第 i 个就不能选第 i-1、i-2 个），转移怎么写？2 7 9 3 1 的答案是多少？
展开练习 3 答案
dp[i] = max(dp[i-1], dp[i-3] + a[i])，i < 3 时第二项的 dp 按 0 计。2 7 9 3 1 → 9（只取第 3 格；9 + 1 不行，因为第 3、5 格只隔一个）。与暴力枚举一致。
练习 4（独立实现）：完成「代码自测」的 decode_count，再加五条断言："100" → 0、"27" → 1、"26" → 2、"2101" → 1、"12120" → 3。
展开练习 4 答案
decode_count 的参考实现（自带断言）
PythonMOD = 10**9 + 7
def ok1(c: str) -> bool:
return c != "0" # 单独成码：1..9 合法，0 不合法
def ok2(c1: str, c2: str) -> bool:
return 10 <= int(c1 + c2) <= 26 # 两位成码：只有 10..26 合法
def decode_count(s: str) -> int:
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # 哨兵：空串一种
for i in range(1, n + 1):
if ok1(s[i - 1]):
dp[i] = dp[i - 1]
if i >= 2 and ok2(s[i - 2], s[i - 1]):
dp[i] = (dp[i] + dp[i - 2]) % MOD
return dp[n]
assert decode_count("12") == 2 # 1|2 / 12
assert decode_count("226") == 3 # 2|2|6 / 22|6 / 2|26
assert decode_count("06") == 0 # 0 不能单独成码，06 也不合法
assert decode_count("10") == 1 # 只能是 10
assert decode_count("0") == 0 # 首字符 0 直接无解
assert decode_count("100") == 0 # 10 之后的 0 无处安放
assert decode_count("27") == 1 # 只能 2|7
assert decode_count("26") == 2 # 2|6 / 26
assert decode_count("2101") == 1 # 只能 2|10|1
assert decode_count("12120") == 3 # 第 05 节手算表十条断言覆盖三条规则的两侧边界。做错最常见的原因：ok2 只写了上界。
练习 5（迁移）：把 P3403 分别按 1 基与 0 基写成两个函数，用 [2, 7, 9, 3, 1]、[1, 2, 3, 1]、[2, 1, 1, 2]、[5] 四组断言确认两者一致；指出 0 基写法比 1 基多了哪一处判断。
展开练习 5 答案
跳格子两种写法的参考实现（自带断言）
Pythondef rob_1based(a):
n = len(a)
dp = [0] * (n + 1) # dp[i] = 前 i 个格子的最高分，dp[0] = 0 是哨兵
for i in range(1, n + 1):
prev2 = dp[i - 2] if i >= 2 else 0
dp[i] = max(dp[i - 1], prev2 + a[i - 1])
return dp[n] # 答案位置：前 n 个
def rob_0based(a):
n = len(a)
if n == 1: # 0 基必须特判：否则 dp[1] 越界
return a[0]
dp = [0] * n # dp[i] = 下标 0..i 的最高分
dp[0] = a[0]
dp[1] = max(a[0], a[1])
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + a[i])
return dp[n - 1] # 答案位置：最后一格
for f in (rob_1based, rob_0based):
assert f([2, 7, 9, 3, 1]) == 12 # 2 + 9 + 1
assert f([1, 2, 3, 1]) == 4 # 1 + 3
assert f([2, 1, 1, 2]) == 4 # 首尾：隔一个取一个的贪心只能得 3
assert f([5]) == 50 基多了 n = 1 的特判和 dp[1] 的单独初始化；1 基靠 dp[0] = 0 把这两处都省掉了。两者答案位置分别是 dp[n-1] 与 dp[n]。
11 / 读题要求与复习自评
两道题的要求对照，以及完成本课之后怎么复习
提交前把下表过一遍；题目页的题面与样例是最终依据。
| 项目 | AI019 标注序列还原计数 | P3403 跳格子 |
|---|---|---|
| 输入 | 一行数字串（1 ≤ |s| ≤ 100000） | 一行空格分隔的非负整数（长度 ≤ 100） |
| 输出 | 方案数对 10⁹ + 7 取模；无解输出 0 | 最高分 |
| 合法条件 | 单独成码 1..9；两位成码 10..26 | 选了第 i 个就不能选第 i-1 个 |
| 哨兵位 | dp[0] = 1 | dp[0] = 0 |
| 答案位置 | dp[n] | dp[n]（1 基）/ dp[n-1]（0 基） |
| 样例 | 12 → 2；226 → 3 | 2 7 9 3 1 → 12；1 2 3 1 → 4 |
需要对照解法时，展开本课第 08 节的完整参考程序；题目页另有思路与参考代码，可在题目页查看。完成条件：本课算完成 = AI019、P3403 两道必做题都通过判题，并勾选全部六条「学习完成检查」；六条检查是自评，勾选不改变题目的通过（AC）状态；复习题单独统计，不影响完成状态。复习时用三个问题自测：① 不看正文，写出 0 的三条规则和各自的拦截位置；② 不看表格，重算 "12120" 的 dp 表；③ 说出跳格子 0 基与 1 基各自的初始化和答案位置。答不出哪一条，就回到对应的节重读，再做第 10 节对应的练习。
基础加练（选做）
同一主题的 3 道基础题
这组题目采用标准输入输出（ACM 模式）：程序从标准输入读取数据、把结果写到标准输出。它们难度低于必做题，适合在必做题之前热身，或在未通过时回来巩固；不计入本课完成标准。每道题给出练习重点、完成标准与提示；已在本站通过的题目会直接显示为已通过。
12 / 练习
按顺序完成本课的任务
必做题已通过 0/2 道
ok1、ok2 两个判断函数测通，再接转移。整段从零写时，最容易在 0 的三条规则上漏判。参考程序在第 08 节的展开区里：先自己写完并提交一次，再展开对照。解码方案计数与合法性判断（decode_count）
代码自测自主练习练习重点：ok1、ok2 两个判断函数 + 哨兵位转移，五个断言覆盖 0 的全部规则；预计用时：15 分钟
完成标准："06"、"0"、"10" 三个含 0 的用例全部正确
需要时查看提示
先写 ok1(c) 和 ok2(c1, c2) 并单独确认：ok2 的下界是 10（"06" 不合法）、上界是 26。断言通过后再接标准输入（sys.stdin）。参考实现在第 10 节练习 4 的展开区。
自测代码（复制到你的代码文件中运行，检查输出是否一致）
MOD = 10**9 + 7
def decode_count(s: str) -> int:
# 你来写：1-26 编码串的还原方案数，无解输出 0，对 MOD 取模
...
assert decode_count("12") == 2 # 1|2 / 12
assert decode_count("226") == 3 # 2|2|6 / 22|6 / 2|26
assert decode_count("06") == 0 # 0 不能单独成码,06 也不合法
assert decode_count("10") == 1 # 只能是 10
assert decode_count("0") == 0 # 首字符 0 直接无解AI019 · 标注序列还原计数
必做任务 1练习重点：把自测函数接上标准输入输出（ACM 模式），逐步取模；预计用时：30 分钟
完成标准：能说出 0 的三条规则各在代码哪一行拦截
需要时查看提示
|s| 可达 10 万：数组写法的时间与空间都是 O(n)；想练滚动变量的，用两个变量代替整条 dp 数组（转移只看前两格，上一课的补充学习讲过压缩条件）。每步对 10**9+7 取模；首字符为 0 时 dp[1] 自然算出 0，不需要提前返回。第 05 节有逐位填表。
P3403 · 跳格子（不取相邻元素的最大和）
必做任务 2练习重点：不能取相邻格子的最大和；0 基与 1 基各写一遍；预计用时：25 分钟
完成标准：两种写法都通过判题，且能对照代码说出各自的答案位置
需要时查看提示
转移 dp[i] = max(dp[i-1], dp[i-2] + a[i])。分数全部非负，答案不会是负数；先手算 n = 1、n = 2。第一遍用 1 基（哨兵位减少边界判断），通过后换 0 基再提交一次，比较两种写法的答案位置。第 07 节把题面示例逐格列出。
提交结果
提交结果说明与处理方法
- WA
答案错误
先测 "0"、"06"、"10"、"100" 四个含 0 的用例；再核对两位码区间是否按题目要求写成 10..26。第 09 节的表给出了每种错误的具体输出。
- RE
运行错误
滚动变量写法不会越界；数组写法检查 i=1 时 dp[i-2] 的处理；跳格子 0 基写法要特判 n = 1。
- TLE
超时
10 万长度下每步都建切片（s[i-2:i]）会慢，改为取字符拼接或直接计算数值。
- PE
格式错误
只输出一个整数，不要把中间的 dp 表一起输出。
- AC
通过
把题目上界从 26 改成 29，指出代码需要改动的是哪一行。如果暂时无法指出，请检查两位数合法性判断函数 ok2 的上界条件。
13 / 学习完成检查
本课学习完成检查
完成本课需要：必做题全部通过，并勾选本课的全部学习完成检查；进阶练习、基础加练与复习题单独统计，不影响完成状态。登录后，勾选记录会保存到账号，并更新课程总览的完成状态。