dp 好题
题单介绍
一些我做过的的 dp 好题。
按时间顺序加入，题单内题目顺序与难度/内容无关。
打 * 的表示我非常推荐一做的题。
题单 $1$：<https://www.luogu.com.cn/training/424182>。
题单 $2$：<https://www.luogu.com.cn/training/471061>。
### 状压 dp
*P2566：很巧妙的状压 dp，运用到了射线法这一 trick。
*CF53E：状压 dp & 计数 dp，难点在于如何去掉重复状态。
P5369：观察性质，巧妙设计状态 & 转移。
P3959：考虑你需要什么信息，合理设计 dp 状态；观察到一些不合法的情况必然不优。
*ARC106E：由 Hall 定理来考虑 dp。
*CF1773G：很牛的状压 dp；观察性质，发现有一些东西根本没有必要状压。
CF1730F：不是很难的状压 dp；考虑你需要什么，考虑什么状态是无用的。
*CF21D：欧拉回路状压 dp。
P10813：转换成 $01$ 序列上的问题，进行 dp。
*ABC216Ex：经典题，LGV 引理+行列式计算拆贡献。
### 计数 dp
*CF53E：状压 dp & 计数 dp，难点在于如何去掉重复状态。
P3643：一般的计数 dp；三倍经验（不完全一样）：ARC104E & CF1295F。
ARC108D：分类讨论，你会惊讶的发现 dp 形式非常简单。
CF1485F：数据范围非常大，但是观察 dp 转移非常有规律。
ABC134F：将问题转换成一个便于转移的模型。
*CF1781F：括号题，考虑括号序列的性质。
CF1542E2：推出一个 dp 形式然后不断优化。
*AGC013E：考虑其组合意义，推出线性的 dp 方程，然后矩乘优化。
CF1327F：按位考虑；想一想自己需要什么，再设计状态 & 转移。
CF1580B：最值问题，考虑笛卡尔树。
CF1559E：容斥，比较综合的题。
*CF1174E：观察性质，然后就做完了。
*CF1765C：很厉害的计数 dp，非常考察选手的 dp 水平。
CF1574F：丢到图论上去考虑；发现有些转移是类似的，考虑怎么加速。
*CF1726E：有关于排列的问题，套路地考虑置换环。
*CF1842G：非常有趣的数数题，考虑组合意义。
*CF1750F：WC2024 上课的题目；正难则反，观察性质。
*ABC262Ex：变换约束条件，ds 优化计数 dp。
*AGC030F：转换模型。
*AGC060C：APIO2024 上课的题，考虑怎么定义状态。
CF1799G：容斥 + dp，比较套路，但也值得一做。
*CF1909F2：考虑几何意义。
CF913F：很综合的 dp 题，有一定难度。
*CF1988F：比较典的 trick，再观察性质。
*P4827：运用多种组合恒等式优化 dp。
*P4709：出公开赛的时候想到的题，完了查重的时候发现了这个题/xk，还算是挺不错的题。
*ARC101E：容斥 + dp。
*P4707：经典题：min-max 容斥 + dp。
*P6596：很厉害的题。
*ABC216Ex：经典题，LGV 引理+行列式计算拆贡献。
*P10013：树形 dp + 树上拓扑序计数。
*P10008：构造双射+dp+拉插。
*P8340：比较优雅的题。
*P10592：观察性质，去掉重复状态。
*P10595：神题。
P5643：trick 大乱炖：树上高消 + min-max 容斥 + FWT。
*AGC038E：min-max 容斥 + dp。
*P8329：容斥 + 连通块 dp。
### 数位 dp
P2481：挺经典 & 巧妙的 trick：拆前/后缀。
*P9129：相当于是在数位上做区间 dp，状态设计 & 转移较为复杂，考察对于 dp 的综合运用。
*P6669：通过 Lucas 定理来划分数位。
### 树形 dp
*P3647：很综合的树形 dp。
*CF1016F：将一棵树看成一条链上挂了好几棵子树，然后做线性 dp；类似 trick 的一个题是 P4151。
CF1485E：先考虑暴力，然后不断减小 dp 状态规模，再是经典的拆绝对值。
CF1626E：先考虑什么情况下能到，然后发现是一个换根 dp 的形式。
*P4383：先考虑去掉 $k$ 的限制怎么做，然后我猜他是凸的。
CF1179D：树上斜率优化 dp。
*CF1830D：观察性质，构造一个相对较优的答案，减少状态数。
*P6326：树上依赖性背包问题。
CF1394D：观察性质，转换答案表达方式，然后进行 dp。
### 经典的 dp 优化
P6190：普通矩阵快速幂优化 dp 的一个变式，考察对于矩阵快速幂优化 dp 的理解。
*CF809D：平衡树优化 dp。
P6773：线段树合并/dsu on tree 优化 dp。
*AGC13E：考虑其组合意义，推出线性的 dp 方程，然后矩乘优化。
ARC108E：树状数组优化 dp。
*CF1662C：矩阵套矩阵，矩阵快速幂优化 dp 好题，P2151 的严格加强版。
P4569：经典的先建 AC 自动机，加字符看成再图上游走，然后就是简单的矩乘优化。
*P4383：先考虑去掉 $k$ 的限制怎么做，然后我猜他是凸的。
CF553E：分治 FFT 加速 dp 转移。
P9871：线段树优化 dp 典题。
CF1179D：树上斜率优化 dp。
*ABC262Ex：变换约束条件，ds 优化计数 dp。
*CF573D：猜测结论，列出 dp 方程，上 ddp。
*ABC240Ex：观察性质，树状数组优化 dp。
*P10145：转换模型，线段树合并优化 dp。
*CF1792F2：观察性质，推出 dp 方程，分治 fft 优化。
*CF2004G：列出转移方程，进行转换，进一步发现可以使用矩乘优化。
*P10013：树形 dp + 树上拓扑序计数。
*ABC305Ex：观察性质 + dp + wqs。
### 其他类型的 dp
P3188：按位考虑，逐个释放空间，观察性质。
P3485：观察到字符集很小，转移时可以做一个“缓存”来优化复杂度。
CF1292C：考虑 mex 的性质，然后在考虑贡献；虽然是树上问题，但感觉不算是树形 dp。
ARC107D：和 P2481 类似。
*CF1765F：很厉害的题，考虑其几何意义，然后是经典 trick：不合法的转移必然不优。
*P9676：观察性质，去掉必然不优的状态。
CF1453F：比较有趣的题，类似于差分的懒标记转移。
*CF1801F：非常好的 dp！整除分块设计状态 & 转移。
*P7606：通过随机化的期望答案来缩小需要枚举信息的范围。
*CF1789F：算得上半个状压 dp，但主要有趣之处在于值域分治。
*ABC211G：变换坐标系；对于后半部分，$\mathcal{O}(nV)$ 做法是很深刻的，或者也可以用 P7606 的 trick。
*CF1768F：观察性质，根号分治。