CSPJ 教学思考：动态规划
引言
动态规划是 CSPJ 拉分的关键知识点。
之所以这样，是因为动态规划不像 DFS、BFS、二分那样有固定的模版格式。学生要在动态规划问题上融汇贯通，需要花费大量的练习，也需要足够的聪明。
笔者自己在高中阶段，也是在动态规划问题上困扰许久。我自己的学习经验是：动态规划还是需要多练，练够 100 道题目，才能够熟悉动态规划的各种变型。之后在比赛中看到新的题目，才会有点似曾相识的感觉，进一步思考出状态转移方程。
所以，我打算写 100 道动态规划方程的题解，希望有志攻破此难关的学生和家长一起加油！
动态规划解题的核心问题
虽然动态规划没有模版可以套，但是动态规划有三个核心问题：
- 状态的定义
- 状态转移方程
- 初始状态的设置
一般思考动态规划就是思考以上三个问题，这三个问题解决了，动态规划的程序也可以写出来了。
教学题目
推荐的教学题目如下：
| 题目名 | 说明 |
|---|---|
| P2842 纸币问题 1 | 基础 DP，记忆化搜索 |
| P1216 数字三角形 | 基础 DP，记忆化搜索 【经典 DP】 |
| P2840 纸币问题 2 | 基础 DP |
| P2834 纸币问题 3 | 基础 DP，有多处可优化的点 |
| P1048 采药 | NOIP2005 普及组第三题。01 背包问题。【经典 DP】 |
| P1616 疯狂的采药 | 完全背包问题。【经典 DP】 |
| P2196 挖地雷 | NOIP1996 提高组第三题。涉及输出路径技巧。 |
| P1434 滑雪 | 上海市省队选拔 2002 |
| P1115 最大子段和 | 最大子段和。【经典 DP】 |
适合的作业：
| 题目名 | 说明 |
|---|---|
| P4017 最大食物链计数 | 记忆化搜索 |
| P2871 Charm Bracelet S | USACO 07 DEC，01 背包 |
| P1802 5 倍经验日 | 01 背包 |
| P1002 过河卒 | NOIP2002 普及组，记忆化搜索 |
| P1049 装箱问题 | NOIP2001 普及组，01 背包 |
| P1064 金明的预算方案 | 01 背包变型，NOIP2006 提高组第二题 |
| P1077 摆花 | NOIP2012 普及组 |
| P1164 小A点菜 | 与摆花一题类似 |
| P2392 考前临时抱佛脚 | 01 背包变型 |
| B3873 小杨买饮料 | 01 背包变型, GESP202309 六级 |
| P13015 学习小组 | 无穷背包，GESP 202506 六级 |
| ｜ P10721 计算得分 ｜ 背包问题变种，GESP 202406 六级 ｜ |
更多的题单：
例题代码
P2842 纸币问题 1
此题可以带着孩子一步步推导和演进。具体步骤如下。
先引导孩子用最暴力的 DFS 的方式来做此题，建立基础的解题框架，虽然会超时，但是也帮助我们后面引导孩子学会记忆化搜索。代码如下：
1 | /** |