DP是提高组的重中之重。
菜鸡 lgswdn 把做到的提高组难度和知识点的一些比较好的dp题整理了一下，希望可以帮到大家qwq。
PS. 对于树形 DP，lgswdn 专门整理了一个 混乱的 题单，戳这儿~。
Caution：这个题单题真的很少，实际上只能带每个版块的入门
UPD：
7/10 增加一道背包 DP。
9/27 修复了已知问题。
10/05 增加了一道背包 DP。
11/9 增加了一道状压 DP。但由于 50 题限制，只在描述中有。
一 区间 DP
区间 DP 是 DP 中比较基础的一种。一般来说可以设 f(l,r) 为区间 [l,r] 的答案。
石子合并 最基础的区间 DP 。
[USACO16OPEN]248 G 和 [USACO16OPEN]262144 P 前一题较为模板，后一题需要状态优化。
[HNOI2010]合唱队 状态需要一些改变（具体化）。
[IOI1998]Polygon 需要分类讨论，80WA 了仔细想一想为什么。
[SCOI2003]字符串折叠 其实很多字符串题目也是区间 DP。
[SCOI2007]压缩 和上面那题有些相似但又不一样。
二 背包 DP
01背包是 DP 的经典，但是提高组选手不应该把目光放在这种题身上，而是应该挑战更加高级的背包。
飞扬的小鸟 背包经典演变问题。
货币系统 这不是小凯的疑惑！但是这道题还是有一定思维难度的。
垃圾陷阱 需要一点点思考。可以用刷表法做。
[BJOI2019]排兵布阵 当你对背包了解了之后，可以用这题练练手。
CF730J Bottles 背包一个很小的变化，第一问很简单，第二问需要稍作转换。
[SHOI2008]循环的债务 打着背包的标签但是还是有点区别的。转移方程比较难一些，状态表示需要用到去除冗余的思想。
[HNOI2007]梦幻岛宝珠 背包的分组优化+二进制的奇怪 DP 合并。
三 单调队列
单调队列是提高组 DP 优化中的考点。相比于其他优化，单调队列没有那么难。单调队列模板和意义默认都会。
[USACO11OPEN]Mowing the Lawn G 单调队列优化 DP 比较模板的题目。
[POI2014]Little Bird 单调队列维护的对象的比较规则中不一定只有一个元素，比如这道题。
CF1077F Pictures with Kittens 理解上面的题目后，这道题可以作为练手题目。
[CSPS2019] 划分 建议做这道题的时候，先想 64 分的 DP。最后需要用 一个贪心，而且这个单调队列还不大一样。
[SBCOI2020] 一直在你身旁 O(n^3) DP 很好想，但是（丢张图）
## 四 树形DP
### 4.1 普通树形 DP
[战略游戏](https://www.luogu.com.cn/problem/P2016) 很简单的树形dp。先想一想在序列上怎么做。
[毛毛虫](https://www.luogu.com.cn/problem/P3174) 进行一定的分类讨论。
[[POI2014]FarmCraft](https://www.luogu.com.cn/problem/P3574) 贪心可以去优化 DP 的转移。
[[POI2011]Dynamite](https://www.luogu.com.cn/problem/P3523) 最大值最小，你想到什么了呢？
### 4.2 树形背包
[有限电视网](https://www.luogu.com.cn/problem/P1273) 树形背包经典题目。
[选课](https://www.luogu.com.cn/problem/P2014) 同样模板题。
[重建道路](https://www.luogu.com.cn/problem/P1272) 稍微难一点点的树形背包。
[[JSOI2018]潜入行动](https://www.luogu.com.cn/problem/P4516) 同样的套路，但是分类讨论烦了一点。
### 4.3 基环树
[城市环路](https://www.luogu.com.cn/problem/P1453) 基环树 DP 模板题。
[[ZJOI2008]骑士](https://www.luogu.com.cn/problem/P2607) 加强版的题目。
[[IOI2008]Island](https://www.luogu.com.cn/problem/P4381) 基环树直径，需要单调队列优化。
### 4.4 二次扫描/换根DP
[[POI2008]Station](https://www.luogu.com.cn/problem/P3478) 模板题一
[CF1092F Tree with Maximum Cost](https://www.luogu.com.cn/problem/CF1092F) 难道上一题加权就不会了吗。
[[USACO10MAR]Great Cow Gathering G](https://www.luogu.com.cn/problem/P2986) 模板题二
[CF708C Centroids](https://www.luogu.com.cn/problem/CF708C) 模型转换，换根DP。
[[APIO2014]连珠线](https://www.luogu.com.cn/problem/P3647) 一道比较难的换根DP。
## 五 期望DP/概率DP
提高组的期望 DP 一般都不难。提高组中有期望在的，除了数学推导，模型转换就是DP。
[OSU!](https://www.luogu.com.cn/problem/P1654) 期望 DP 的经典题目。
[换教室](https://www.luogu.com.cn/problem/P1850) 提高组期望 DP 真题。
[[SHOI2014]概率充电器](https://www.luogu.com.cn/problem/P4284) 换根 DP 中的期望 DP，难度不小。
## 六 DP 混杂在一起
一个略微综合的板块，但是不是很难。
[[SCOI2009]粉刷匠](https://www.luogu.com.cn/problem/P4158) 背包DP&区间DP。
[[ZJOI2006]物流运输](https://www.luogu.com.cn/problem/P1772) 区间DP&最短路。
## 七 状压DP
状压DP的第一个用处是正经做题，第二个用处是一种很常见的暴力。
[[USACO06NOV]Corn Fields G](https://www.luogu.com.cn/problem/P1879) 最模板的板子题。
[[NOI2001]炮兵阵地](https://www.luogu.com.cn/problem/P2704) 上古的 NOI 状压板子二。
[宝藏](https://www.luogu.com.cn/problem/P3959) 提高组考过的真题
[[USACO12MAR]Cows in a Skyscraper G](https://www.luogu.com.cn/problem/P3052) 状态压缩中枚举子集。
[[APIO2007]动物园](https://www.luogu.com.cn/problem/P3622) 数据范围没有状压的标志，但是题目中却另有一个可以状压的东西。有很多有趣的小技巧。
## 八 小测验
一个的 DP 题组成的小测验，建议上述题做完后来 AK。（注意：题目顺序对应了大致难度排序）
T1 [能量项链](https://www.luogu.com.cn/problem/P1063)
T2 [子串](https://www.luogu.com.cn/problem/P2679)
T3 [Promis I Can't Keep](https://www.luogu.com.cn/problem/P6554)
T4 [(POI)Triumphal arch](https://www.luogu.com.cn/problem/P3554)
T5 [Emiya家今天的饭](https://www.luogu.com.cn/problem/P5664)
T6 [(POI)Hotel](https://www.luogu.com.cn/problem/P3565) （放在第六题主要原因，建议去思考一下长链剖分的做法）