DP
题单介绍
（注：题单中后五题着重于考察DP的优化）
## 1 近三年真题录
1. CSP-S 2021 B 括号序列（区间 DP）（强制 / 钦定的技巧）
2. CSP-S 2022 D 数据传输（树上 DP）（矩乘优化）
3. NOIP 2021 B 数列（数位 DP + 二进制）（只计 log n 位影响）
4. NOIP 2021 C 方差（差分结论 + DP）
5. NOIP 2022 C 建造军营（树上 DP + 双连通分量）
6. NOIP 2023 C 双序列拓展（DP + 发现性质）
7. NOIP 2023 D 天天爱打卡（DP + 线段树优化）
## 2 题目特点
1. 每年 1 ∼ 2 考。各种常见类型的 DP 都有概率出现。
2. 几乎不会是签到题，一般放在后两题位置。
3. 若结合其他算法考察，则思维上较为套路而码量略大（如矩乘优化，线段树优化）；若
不结合其他算法，则重点考察转化技巧 / 隐藏结论 / 严谨分析的功夫，思维量高而码量略小。
## 3 建议
1. 找题：在知识体系和推导能力建立前，盲目地训练真题收效很小，真题都是以区分选手
为主要目的。见识多一些类型的 DP 题目，找些质量高的题单加以训练才是真谛。
2. 做题：每一道题涉及的技巧与结论要能够独立完整的推导，而非停留在似是而非的“理
解”。
3. 总结：刷题过程中，补全自己的“推理工具箱”+ “数学知识”，对当下流行的技巧要
多些关注。要愿意花时间。别仅停留在模板阶段！