椰程信奥 · 教案
动态规划1 · 教案
课题
CSP复赛专题16 · 动态规划1（背包 + 线性DP） —— 对应视频 35′25″，课件 15 页 配套《限时训练单》50 分钟
教学目标
| 维度 | 内容 |
|---|
| 知识与技能 | ① 说出 DP 三大特性；② 独立完成 01 背包与完全背包的一维实现（循环方向正确）；
③ 写出 LIS、LCS 的状态定义与转移方程。 |
| 过程与方法 | 通过倒序/正序对照实验，自主归纳"01 倒序、完全正序"。 |
| 情感态度价值观 | 体会"定义决定一切"——DP 里状态定义错了，代码再漂亮也没用。 |
教学重难点
重点：01 背包与完全背包的一维循环方向；LIS/LCS 的状态定义。
难点：理解"倒序让 dp[j−w] 停留在上一轮"这一句话的物理含义。
教学过程
| 环节 | 页码 | 教师活动 | 学生活动 | 设计意图 |
|---|
| 引入 | P2 | 三大特性 + 五步法 | 判断题 | 建立方法论 |
| 01 背包 | P3–5 | 建模、动画①② | 猜 + 验证 | 抓住方向 |
| 完全背包 | P6 | 动画③对照 | 口述原理 | 形成对比 |
| LIS | P7–8 | 状态定义、动画④ | 举反例 | 突破难点 |
| LCS | P9–10 | 二维转移、动画⑤ | 口述转移 | 拓展二维 |
| 实战 | P11–12 | 动画⑥ + 检测 | 独立完成 | 形成性评价 |
板书设计
DP 五步：定状态 → 写转移 → 定初值 → 定顺序 → 定答案
01 背包：for j = T → w dp[j]=max(dp[j], dp[j−w]+v) ★倒序
完全背包：for j = w → T dp[j]=max(dp[j], dp[j−w]+v) ★正序
LIS：d[i] = 以 i 结尾的最长长度；答案 = max(d)
LCS：相等 → dp[i−1][j−1]+1；不等 → max(上, 左)
易错预警
① 01 背包写成正序（变完全背包，答案虚高）；② 完全背包写成倒序（变 01，答案偏小）；
③ LIS 答案取 d[n]（应为 max(d)）；④ 完全背包价值未用 long long；
⑤ 导弹拦截把 ">=" 写成 ">"（6 变 5）。
作业
- 必做：OJ 题包 HERB（采药）、HERB2（疯狂的采药）、MISSILE（导弹拦截），要求 AC。
- 选做：用"最少插入字符变回文"（原串反转求 LCS）验证 LCS 的理解。