01 / 本课学习路线
本课学习路线
阅读与推演约 112 分钟，练习约 65 分钟
02 / 学习目标与先修自测
学完本课你能做什么，以及开始前需要会什么
本课只教一件事：动手写代码前先写五行注释——状态、转移、初始化、遍历顺序、答案位置。
| 学完后能做的事 | 正文位置 | 检查方式 |
|---|---|---|
| 不看笔记写出五要素的五句话，并对任一题逐条说明，通过（AC）P3399 | 第 03、04 节 | 自查第 2 条、必做任务 1 |
| 解释递归爬楼梯为什么慢、递推为什么每个子问题只算一次 | 第 03 节 | 自查第 3 条 |
| 说出「走到第 i 级」与「走完前 i+1 级」两种状态的答案位置差别 | 第 05 节 | 自查第 4 条、练习 5 |
| 转移里的缺项（越界下标）有显式判断，而不是依赖负下标 | 第 07 节 | 自查第 5 条 |
| 写对带约束的转移（跳过回退 3 轮），通过 P3394 | 第 06、08 节 | 必做任务 2 |
先修自测：下面 5 题请先自己写答案，再展开对照。答不出的按括号里的位置补看再回来。本课假定你已完成模块 1 的「标准输入输出」与模块 2 的「前缀和」。
展开先修自测答案
自测 1：f[n] = f[n-1] + f[n-2]，f[0] = 1（原地不动算一种）、f[1] = 1。本课把 2 换成 3 就是猴子爬山。
自测 2：n + 1 个元素，下标 0..n——所以答案可以放在 dp[n]。
自测 3：7 与 5（负下标从末尾数）；dp[-4] 抛 IndexError。转移里出现 dp[i-3] 且 i < 3 时，Python 不会报错而是悄悄取到末尾——第 07 节的错误表。
自测 4：0。P3394 里「取本轮得 -2、跳过得 0」取较大者就是这一步。
自测 5：[int(x) for x in input().split(",")]。P3394 的输入正是一行逗号分隔。
03 / 概念与术语
状态、转移、初始化、遍历顺序、答案位置；递归为什么慢
动态规划的核心只有一句：把答案写成「更小规模同类问题的答案」的函数，再按从小到大的顺序把每个规模算一次、存起来。
| 要素 | 含义 | 代码里的位置 |
|---|---|---|
| ① 状态 | dp[i] 表示什么——一句话，主语、宾语都要有 | 注释第一行；决定数组长度 |
| ② 转移 | dp[i] 由哪些更小的格子算出来；缺项怎么办 | 循环体里的那一行（或几行） |
| ③ 初始化 | 最小规模的答案，直接给值 | 循环之前 |
| ④ 遍历顺序 | 保证算 dp[i] 时它依赖的格子已经算好 | for i in range(…) 的方向 |
| ⑤ 答案位置 | 由状态定义唯一决定：是 dp[n] 还是 dp[n-1] | print(...) 那一行 |
| 子问题 | 同一个问题在更小规模上的实例 | 每个 dp[i] |
| 重复计算 | 朴素递归把同一个子问题算很多次 | 见下面的调用次数表 |
| n | 递归调用次数 | 不同的子问题数 |
|---|---|---|
| 10 | 109 | 10 |
| 20 | 13,529 | 20 |
| 40 | 204,668,309 | 40 |
递推把每个子问题算一次并存进 dp，40 阶只要 40 步；朴素递归 2 亿次调用在 2 秒时限内跑不完。补看：爬楼梯动画。
补充学习（选学）递归为什么慢：数一数重复计算的次数约 5 分钟同一个子问题被计算了多少次
朴素递归函数 climb（爬楼梯方法数）的调用次数：climb(n) = climb(n-1) + climb(n-2)，n = 10 是 109 次，n = 20 是 13,529 次，n = 40 是 204,668,309 次——2 亿次调用，Python 在 2 秒时限内跑不完。而 n = 40 时不同的子问题总共只有 40 个。
改进有两个方向。自顶向下：保留递归，加一层缓存装饰器（functools.lru_cache），一行即可。自底向上：从 dp[1] 顺序推到 dp[n]，也就是正文的递推写法。两种写法的子问题数量相同；机考中递推更常用，因为它不受递归深度限制，需要时还能进一步压缩空间。
补充学习（选学）状态压缩：什么时候可以不保存整个 dp 数组约 4 分钟转移只用到最近几格时，可以压缩成几个变量
先看转移方程读取了哪些格子。爬楼梯只用 dp[i-1] 和 dp[i-2]，猴子爬山还要用 dp[i-3]。转移最远读到几格之前，就至少保留几个变量滚动更新；更早的格子不会再被读取，可以不保存。
也有不能压缩的情况：转移需要读取任意更早格子的题（例如凑金额类），数组必须保留。判断时看两点：转移最远读到哪一格，就至少保留到哪一格；压缩之后还要确认更新顺序不会覆盖本轮仍要读取的旧值。这两点会在网格动态规划（模块 4 · 第 3 课）和 0/1 背包（模块 4 · 第 4 课）两课各验证一次。
04 / 五要素与填表：P3399
先写五句话，再写循环
P3399「猴子爬山」：一个整数 n（0 ≤ n ≤ 50），每次只跳 1 步或 3 步，输出到第 n 级的不同跳法数。题面示例：50 → 122106097；3 → 2。五要素：① 状态 f[i] = 走到第 i 级的方法数；② 转移 f[i] = f[i-1] + f[i-3]（最后一步走 1 级或 3 级，i < 3 时缺项按 0）；③ 初始化 f[0] = 1（原地不动算一种走法）；④ 遍历顺序 i 从 1 到 n 递增；⑤ 答案位置 f[n]。
| i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| f[i] | 1 | 1 | 1 | 2 | 3 | 4 |
| 来源 | 初始 | f[0] | f[1] | f[2]+f[0] | f[3]+f[1] | f[4]+f[2] |
验证两格：f[3] = f[2] + f[0] = 1 + 1 = 2（三个 1 步，或一个 3 步）；f[5] = f[4] + f[2] = 3 + 1 = 4（1+1+1+1+1、3+1+1、1+3+1、1+1+3）。先用手算表检查程序输出，再通过边界用例验证转移和初始化。
继续填到 n = 8，并核对题面示例
f[6] = f[5] + f[3] = 4 + 2 = 6 f[7] = f[6] + f[4] = 6 + 3 = 9 f[8] = f[7] + f[5] = 9 + 4 = 13 n = 0 → 1（起点本身）；n = 50 → 122106097（题面示例） 数列增长约每步 ×1.47，n = 50 时约 1.2×10⁸，Python 整数不溢出；用 C++/Java 时 int 也放得下（< 2³¹）
动态规划练习模板：五要素注释与循环
Python# 动态规划练习模板：先写完五行注释，再写循环体
import sys
def solve() -> None:
data = sys.stdin.read().split()
# 待完成 0：按题目格式读入（P3399 是一个整数 n；P3394 是一行逗号分隔的分数）
# ① 状态：dp[i] = ____
# ② 转移：dp[i] = ____（缺项如何处理：i-3 < 0 时怎么办）
# ③ 初始化：dp[0] = ____
# ④ 遍历顺序：i 从 ____ 到 ____
# ⑤ 答案位置：____（与①对照后再确定是 dp[n] 还是 dp[n-1]）
n = ...
dp = [0] * (n + 1)
for i in range(1, n + 1):
pass # 待完成 1：按②写出这一行的转移
print(dp[n]) # 待完成 2：按⑤核对答案位置
solve()先写完五行注释，再写循环体。答案位置那一行留了待填项：和你的状态定义对照后，再确定是 dp[n] 还是 dp[n-1]。
05 / 答案位置由状态定义唯一决定
同一道题的两种状态定义：f[n] 与 g[n-1]
把状态换成 g[i] = 走完前 i+1 级的方法数（0 基），n 级台阶的答案在 g[n-1]，不在 g[n]。两种定义都正确，混用会出错。
| 下标 i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| f[i]（走到第 i 级） | 1 | 1 | 1 | 2 | 3 | 4 ← 答案 |
| g[i]（走完前 i+1 级） | 1 | 1 | 2 | 3 | 4 ← 答案 | — |
g 比 f 整体左移一格：g[i] = f[i+1]。写五要素时把状态定义和答案位置一起写完、互相对照，不要写完代码再回头猜答案在哪一格。第 09 节错误表给出了「按 f 写转移、按 g 取答案」的输出。
第五要素：答案位置由状态定义唯一决定
写完五行注释后做一次对照：状态里写的「第 i 级」是不是就是答案要问的「第 n 级」？是 → dp[n]；状态是「前 i+1 个」→ dp[n-1]。练习 5 会让你把 P3399 按 0 基定义重写一遍。
06 / 带约束的转移：P3394
取本轮加分，跳过回到 3 轮前；前 3 轮跳过置 0
P3394「玩牌高手」：一行逗号分隔的 n 个分数（1 ≤ n ≤ 20，−100 ≤ 分数 ≤ 100）；每轮可以取本轮牌面（总分加上它），也可以跳过——总分变回 3 轮前的总分，第 1、2、3 轮跳过则置 0；初始 0 分、必须依次参加；输出最高总分。题面示例：1,-5,-6,4,3,6,-2 → 11；0,0,0 → 0。
| 轮 i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| a[i] | 1 | −5 | −6 | 4 | 3 | 6 | −2 |
| 取分 dp[i-1]+a[i] | 1 | −4 | −6 | 4 | 7 | 13 | 11 |
| 跳过 dp[i-3] | 0 | 0 | 0 | dp[1] = 1 | dp[2] = 0 | dp[3] = 0 | dp[4] = 4 |
| dp[i] | 1 | 0 | 0 | 4 | 7 | 13 | 11 |
dp[2] = max(1 − 5, 0) = 0、dp[3] = max(0 − 6, 0) = 0：第 2、3 轮跳过；dp[7] = max(13 − 2, dp[4] = 4) = 11 → 输出 11，与题面一致。「跳过」不是「本轮不加分」，而是回到 3 轮前的总分——两者在连续负分段上结果不同（第 09 节错误表）。
| 轮 i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| a[i] | 1 | -5 | 2 | 4 | 3 |
| 取分 dp[i-1]+a[i] | 1 | -4 | 2 | 6 | 9 |
| 跳过 dp[i-3] | 0 | 0 | 0 | 1 | 0 |
| dp[i] | 1 | 0 | 2 | 6 | 9 |
dp[2] = max(1 + (-5), 0) = 0：取第 2 轮的 -5 会降低总分，跳过更优。dp[5] = max(6 + 3, dp[2] = 0) = 9。全部为负（-1,-2,-3,-4）时每轮都跳过，答案 0；0,0,0 → 0。
五要素：① dp[i] = 前 i 轮结束后的最高总分（1 基，dp[0] = 0）；② dp[i] = max(dp[i-1] + a[i], dp[i-3])，i ≤ 3 时第二项取 0；③ dp[0] = 0；④ i 从 1 到 n；⑤ dp[n]。题目页参考题解用 0 基数组、i < 3 时与 0 取最大，与这里等价。
07 / 缺项与负下标
转移读到不存在的格子时，要显式判断，不能依赖负下标
f[i-3] 在 i < 3 时不存在。Python 里 f[-1]、f[-2] 不会报错，而是取到数组末尾——程序看起来正常，答案却可能错。
两种写法在 n = 5 与 n = 1、2 上的表现
显式判断: if i >= 3: f[i] += f[i-3] → n = 5 时 f = [1,1,1,2,3,4]，输出 4；n = 1 → 1；n = 2 → 1 不判断: f[i] += f[i-3]（n = 5：i=1 读 f[-2]=f[4]=0、i=2 读 f[-1]=f[5]=0 —— 这两格还没填，仍是 0）→ 恰好也输出 4 n = 1 就错: 数组只有 f[0]、f[1] 两格，i=1 读 f[-2] 就是 f[0]=1 → f[1] = 1 + 1 = 2（期望 1） n = 2 也错: i=1 读 f[-2]=f[1]（刚写成 1）→ f[1]=2；i=2 读 f[-1]=f[2]（刚写成 2）→ f[2]=4（期望 1） 为什么要判断: 负下标绕回去读到的格子「恰好还是 0」只在数组够长时成立；n 小于 3 时绕回到刚填好的格子，答案翻倍；C++/Java 负下标直接越界
判断的写法只有两种：在转移里 if i >= 3 才加那一项；或者把数组开长、把「不存在」的格子明确初始化为该题的缺省值（计数题是 0，最大值题可能是负无穷）。不要靠语言的默认行为。
08 / 从五行注释到程序
两道必做题的完整参考程序，每一步落在哪几行
先自己写完并提交一次，再展开对照。
| 要素 | P3399 | P3394 |
|---|---|---|
| ① 状态 | f[i] 到第 i 级的方法数 | dp[i] 前 i 轮结束后的最高总分 |
| ② 转移 | f[i] = f[i-1]；if i >= 3: f[i] += f[i-3] | take = dp[i-1] + a[i-1]；skip = dp[i-3] if i >= 3 else 0；dp[i] = max(take, skip) |
| ③ 初始化 | f[0] = 1 | dp[0] = 0 |
| ④ 遍历顺序 | for i in range(1, n + 1) | 同左 |
| ⑤ 答案位置 | print(f[n]) | print(dp[n]) |
展开完整参考程序 1：P3399 猴子爬山（先自己写完并提交一次，再展开对照）
完整程序：P3399（标准输入 → 标准输出）
Pythonimport sys
n = int(sys.stdin.readline().strip())
f = [0] * (n + 1)
f[0] = 1 # ① 状态 f[i] = 到第 i 级的方法数；③ 起点算一种
for i in range(1, n + 1): # ④ 从小到大
f[i] = f[i - 1] # ② 最后一步走 1 级
if i >= 3:
f[i] += f[i - 3] # ② 最后一步走 3 级（i < 3 时缺项按 0）
print(f[n]) # ⑤ 答案在 f[n]自测建议：题面示例（50 → 122106097、3 → 2）、n = 0 → 1、n = 5 → 4。
展开完整参考程序 2：P3394 玩牌高手
完整程序：P3394（标准输入 → 标准输出）
Pythonimport sys
a = [int(x) for x in sys.stdin.readline().strip().split(",")] # 一行逗号分隔的分数
n = len(a)
dp = [0] * (n + 1) # dp[i] = 前 i 轮结束后的最高总分（1 基），dp[0] = 0
for i in range(1, n + 1):
take = dp[i - 1] + a[i - 1] # 取本轮牌面
skip = dp[i - 3] if i >= 3 else 0 # 跳过：回到 3 轮前的总分；前 3 轮跳过置 0
dp[i] = max(take, skip)
print(dp[n])自测建议：题面两组示例（11 / 0）、第 06 节第二组（9）、全负数（0）；想进一步验证，可写一个「枚举每轮取 / 跳过」的全枚举，用短输入对拍。输入是一行逗号分隔。
09 / 边界、反例与复杂度
错误做法在具体输入上各输出什么
下面每一行都是一个具体的错误程序，给出输入、错误输出与正确输出；把参考程序改成对应写法就能复现。
| 错误做法 | 输入 | 错误输出 | 正确输出 | 判题结果 |
|---|---|---|---|---|
| P3399 初始化 f[0] = 0（起点不算一种） | 5 | 0 | 4 | 答案错误（WA） |
| P3399 按 f 写转移、按 g 取答案（输出 f[n-1]） | 5 | 3 | 4 | 答案错误（WA） |
| P3394 把「跳过」写成「本轮不加分」（skip = dp[i-1]） | 题面示例 | 14 | 11 | 答案错误（WA） |
| P3394 按空格拆逗号行 | 题面示例 | 抛出 ValueError | 11 | 运行错误（RE） |
| 朴素递归不加缓存 | 50 | 结果正确但约 10⁹ 次调用 | 同左 | 超时（TLE） |
第三行的 14：允许「跳过但保留总分」等于只加正数：1 + 4 + 3 + 6 = 14；真实规则跳过会回退到 3 轮前，所以第 4 轮取 4 时只能接在 dp[3] = 0 上。
| 做法 | 时间 | n = 50 / 20 时 |
|---|---|---|
| 递推填表 | O(n) | 50 步 / 20 步 |
| 递归 + 缓存 | O(n) | 同上，但受递归深度限制 |
| 朴素递归 | 指数级 | n = 50 约 10⁹ 次调用，超时 |
10 / 渐进练习与参考答案
跟做 → 改一个条件 → 独立实现 → 迁移
每题先在纸上或文件里做完，再展开答案。
练习 1（跟做）：按第 04 节表的格式把猴子爬山填到 n = 8，写出每一格的来源。
展开练习 1 答案
f = [1, 1, 1, 2, 3, 4, 6, 9, 13]：f[6] = f[5] + f[3] = 6，f[7] = f[6] + f[4] = 9，f[8] = f[7] + f[5] = 13。做错最常见的原因：把 f[i-3] 看成 f[i-2]。
练习 2（改一个条件）：步幅改成 1 或 2 级，五要素哪一条变了？n = 5 的答案是多少？
展开练习 2 答案
只有转移变：f[i] = f[i-1] + f[i-2]（i ≥ 2 才加第二项）。f = [1, 1, 2, 3, 5, 8] → 8。状态、初始化、遍历顺序、答案位置都不变。
练习 3（改一个条件）：P3394 改成「跳过回到 2 轮前，前 2 轮跳过置 0」，题面示例的输出是多少？
展开练习 3 答案
dp[i] = max(dp[i-1] + a[i], dp[i-2])，i ≤ 2 时第二项 0。逐轮：1、0、1、5、8、14、12 → 12。只改转移里回退的格数与阈值。
练习 4（独立实现）：完成「代码自测」的 climb13，再加两条断言：n = 8 应为 13，n = 50 应为 122106097。
展开练习 4 答案
climb13 的参考实现（自带断言）
Pythondef climb13(n):
f = [0] * (n + 1)
f[0] = 1 # 起点算一种走法
for i in range(1, n + 1):
f[i] = f[i - 1] # 最后一步走 1 级
if i >= 3:
f[i] += f[i - 3] # 最后一步走 3 级；i < 3 时这一项不存在
return f[n]
assert climb13(0) == 1
assert climb13(3) == 2 # 1+1+1 / 3
assert climb13(5) == 4 # 手推表最后一格
assert climb13(8) == 13 # 练习 1 的表
assert climb13(50) == 122106097 # 题面示例
def climb13_zero_based(n): # 状态换成 g[i] = 走完前 i+1 级的方法数
if n == 0:
return 1
g = [0] * n
for i in range(n):
level = i + 1 # 第 i 格对应「走完前 i+1 级」
g[i] = (g[i - 1] if i >= 1 else 1) + (g[i - 3] if i >= 3 else (1 if level == 3 else 0))
return g[n - 1] # 答案位置随定义变成 g[n-1]
assert climb13_zero_based(3) == 2 and climb13_zero_based(5) == 4 and climb13_zero_based(8) == 13前五条断言是 1 基定义；后面的 climb13_zero_based 是练习 5 的 0 基定义，答案在 g[n-1]。
练习 5（迁移）：把 P3399 按「g[i] = 走完前 i+1 级的方法数」重写：初始化怎么写、答案在哪一格？用 n = 3、5、8 验证与 f 版一致。
展开练习 5 答案
g[0] = 1（走完 1 级只有 1 步）、g[1] = 1、g[2] = 2（走完 3 级：1+1+1 或 3）；之后 g[i] = g[i-1] + g[i-3]；答案在 g[n-1]。n = 3 → g[2] = 2，n = 5 → g[4] = 4，n = 8 → g[7] = 13，与 f 版一致。参考实现见练习 4 展开区的第二个函数。
11 / 读题要求与复习自评
两道题的要求对照，以及完成本课之后怎么复习
提交前把下表过一遍；题目页的题面与样例是最终依据。
| 项目 | P3399 猴子爬山 | P3394 玩牌高手 |
|---|---|---|
| 输入 | 一个整数 n（0 ≤ n ≤ 50） | 一行逗号分隔的分数（1 ≤ n ≤ 20，−100..100） |
| 输出 | 跳法数 | 最高总分 |
| 状态 | f[i] 到第 i 级的方法数 | dp[i] 前 i 轮的最高总分 |
| 转移 | f[i-1] + f[i-3]（i < 3 缺项 0） | max(dp[i-1] + a[i], dp[i-3])（i ≤ 3 第二项 0） |
| 样例 | 50 → 122106097；3 → 2 | 1,-5,-6,4,3,6,-2 → 11；0,0,0 → 0 |
需要对照解法时，展开本课第 08 节的完整参考程序；题目页另有思路与参考代码，可在题目页查看。完成条件：本课算完成 = P3399、P3394 两道必做题都通过判题，并勾选全部六条「学习完成检查」；六条检查是自评，勾选不改变题目的通过（AC）状态；复习题单独统计，不影响完成状态。复习时用三个问题自测：① 不看正文，写出猴子爬山的五要素；② 不看表格，重算题面示例 1,-5,-6,4,3,6,-2 的 dp 表；③ 说出把状态换成 0 基后答案在哪一格。答不出哪一条，就回到对应的节重读，再做第 10 节对应的练习。
基础加练（选做）
同一主题的 2 道基础题
这组题目采用标准输入输出（ACM 模式）：程序从标准输入读取数据、把结果写到标准输出。它们难度低于必做题，适合在必做题之前热身，或在未通过时回来巩固；不计入本课完成标准。每道题给出练习重点、完成标准与提示；已在本站通过的题目会直接显示为已通过。
12 / 练习
按顺序完成本课的任务
必做题已通过 0/2 道
1 步或 3 步爬楼梯（climb13）：五要素练习
代码自测自主练习练习重点：按五要素从零写 1 步 / 3 步爬楼梯，用断言对照手算表；预计用时：15 分钟
完成标准：断言全部通过，且能说出把状态换成 0 基后答案下标怎么变
需要时查看提示
f[0] = 1 起步，i < 3 时 f[i-3] 按 0 计（写 if i >= 3 才加）。三个断言对应手算表的三格。参考实现在第 10 节练习 4 的展开区。
自测代码（复制到你的代码文件中运行，检查输出是否一致）
def climb13(n):
# 你来写：每次走 1 步或 3 步，到第 n 级的方法数（f[0]=1）
...
assert climb13(0) == 1
assert climb13(3) == 2 # 1+1+1 / 3
assert climb13(5) == 4 # 手推表最后一格
# 通过后再想：把状态换成「走完前 i+1 级」，答案下标怎么变？P3399 · 猴子爬山
必做任务 1练习重点：把自测的 climb13 接上标准输入输出（ACM 模式）；预计用时：20 分钟
完成标准：能不看笔记说出五要素的五句话
需要时查看提示
和自测函数同一套逻辑，只补读入和打印。方法数按类斐波那契数列增长，n = 50 约 1.2×10⁸，Python 整数不会溢出；用 C++ 或 Java 时先估算量级再选类型。第 04 节有逐格填表。
P3394 · 玩牌高手
必做任务 2练习重点：带约束的转移：跳过回退 3 轮，前 3 轮跳过按 0 计；预计用时：30 分钟
完成标准：能解释 dp[2] 为什么等于 0 而不是 -4
需要时查看提示
输入是一行逗号分隔。dp[i] = max(dp[i-1] + a[i], dp[i-3])，i ≤ 3 时第二项取 0。「跳过」不是「本轮不加分」，而是回到 3 轮前的总分；两者在连续负分段上结果不同。第 06 节把题面示例逐轮列出。
提交结果
提交结果说明与处理方法
- WA
答案错误
优先检查三处：初始化与状态含义不一致、缺项（i-3 < 0）没有拦截、答案位置下标取错。先用 n = 0、1、2 手算对照——第 09 节的表给出了每种错误的具体输出
- RE
运行错误
dp[i-1]、dp[i-3] 在开头几轮会越界；Python 负下标不报错但取错值，更难发现；P3394 的逗号行不要用不带参数的
split()- TLE
超时
递归不加缓存是指数级调用次数；本课两道题的递推都是 O(n)，超时先检查读入方式。
- AC
通过
把 dp 表打印一行，和手算表对照一遍，再说明答案落在这一格的原因
13 / 学习完成检查
本课学习完成检查
完成本课需要：必做题全部通过，并勾选本课的全部学习完成检查；进阶练习、基础加练与复习题单独统计，不影响完成状态。登录后，勾选记录会保存到账号，并更新课程总览的完成状态。