椰程信奥 · 教案
动态规划2 · 教案
课题
CSP复赛专题17 · 动态规划2（区间DP + 线性DP进阶） —— 对应视频 23′48″，课件 14 页
教学目标
| 维度 | 内容 |
|---|
| 知识与技能 | ① 说出区间 DP 三层循环（长度→起点→分割点）；② 完成最长回文子串；
③ 完成二叉排序树计数（含空区间初值）；④ 用"反转 + LCS"求回文词最少插入数。 |
| 过程与方法 | 通过错误顺序的可视化演示，形成"先检查依赖是否就绪"的习惯。 |
| 情感态度价值观 | 体会算法中"顺序即正确性"。 |
教学重难点
重点：区间 DP 的填表顺序与初值；乘法/加法原理在 BST 计数中的应用。
难点：区分"回文子串（区间DP，连续）"与"回文词（LCS，可插入）"。
教学过程
| 环节 | 页码 | 教师活动 | 学生活动 | 设计意图 |
|---|
| 引入 | P2 | 三层循环套路 | 背诵 | 建立骨架 |
| 顺序 | P3 | 动画①对照 | 找错 | 突破难点 |
| 回文子串 | P4–5 | 建模 + 动画② | 口述转移 | 第一道题 |
| BST | P6–7 | 两原理 + 动画③ | 解释初值 | 第二道题 |
| 回文词 | P8–9 | LCS 应用 + 动画④ | 辨析 | 打通线性DP |
| 检测 | P10–11 | 辨析 + 四题 | 独立完成 | 形成性评价 |
板书设计
区间 DP 三层：len → i → k（长度 / 起点 / 分割点）
回文子串：dp[i][j] = (s[i]==s[j]) && (len==2 || dp[i+1][j−1])
BST 计数：dp[i][j] = Σ dp[i][k−1] × dp[k+1][j] ★ dp[i][j]=1 当 i>j
回文词：答案 = n − LCS(s, reverse(s))
易错预警
① 第一层写成 i（依赖未就绪）；② 空区间初值漏掉（答案全 0）；
③ 用 LCS 求回文子串；④ 卡特兰数爆 int（用 long long）。
作业
- 必做：OJ 题包 PALIN（最长回文子串）、BST（二叉排序树计数），要求 AC。
- 选做：实现"最少插入字符变回文"，并与 LCS 模板对照。