题单链接
这是 AT 之前办的一场 DP 专题，里面都是很经典的问题，可以帮助大家复习 DP 的套路，个人感觉对于巩固基础来说质量很高，建议大家去去联系一下，尽量不要看题解。
本博客只讨论了绿色及以上难度的题目，下面是我的题解。
I Coins
设 \(f_{i,j}\) 表示扔到了第 \(i\) 个，有 \(j\) 个是正面的概率，然后完了。
J Sushi
这题不能顺推，设 \(f_{i,j,k}\) 表示剩 \(i,j,k\) 个 \(1,2,3\) 盘子时到达目标的期望步数，转移就分讨，然后化简下式子，即可。如果是递推的形式，必须要注意顺序 \(k,j,i\)，否则会有后效性，写记搜会很方便。
我不会这道题，并且拿给几个人做也不会，很好的题目，让我想起来当初学概率期望的时候，现在想来确实忘记了很多套路，这题只要想到倒着做就没什么了，看起来大家都忘了。
M Candies
设 \(f_{i,j}\) 表示分到第 \(i\) 个人，还剩 \(j\) 颗糖的方案数，\(\mathcal{O}(K)\) 转移即可。
O Matching
设 \(f_{i,s}\) 表示到第 \(i\) 个左部点，右部点点的匹配情况为 \(s\) 时的方案数，这样 \(\mathcal{O}(n^22^n)\) 就做完了，但是这个不是正解，匹配的顺序不重要，并且两端匹配人数一直是相等的，所以不妨钦定是最后一个左部点在匹配，只要考虑匹配状态即可，设 \(f_{s}\) 表示右部点匹配情况为 \(s\) 时的方案数，直接枚举右部点，跟第 \(\text{popcount}(s)\) 个左部点匹配即可，这样时间复杂度就是 \(\mathcal{O}(n2^n)\) 了。
P Independent Set
设 \(f_{i,0/1}\) 表示 \(i\) 的子树内，\(i\) 为白/黑色时的方案数。
Q Flowers
找最大上升子序列即可。
R Walk
路径方案数的式子是经典的矩阵形式，矩阵快速幂即可。
S Digit Sum
数位 DP 板子。
T Permutation
有关排列 DP 的经典套路，设 \(f_{i,j}\) 表示到 \(i\)，只考虑排列 \([1,i]\)，以 \(j\) 结尾的方案数，转移就是直接考虑填的数在上一个排列中的位次，前缀和优化即可，这题肯定也能连续段 DP，但是我不会。
U Grouping
设 \(f_{s}\) 表示所有组的集合是 \(s\) 的最大价值，\(3^n\) 枚举子集即可。
V Subtree
设 \(f_i\) 表示 \(i\) 的子树内，\(i\) 是黑点且与子节点中的黑点相通的方案数，DP 完一遍后考虑换根，设 \(g_i\) 表示 \(i\) 节点为黑色，并且与子树外相通的方案数，\(ans_i=f_ig_i\)，考虑如何求得 \(g_i\)，正常套路肯定是拆贡献，但是这题模数任意，不能求逆元，这种情况往往考虑前缀积后缀积，求得前缀积后缀积之后，直接考虑拆掉父亲的贡献来求 \(g_i\) 即可。
这题我一开始想的比较复杂，并且换根时没有想到前缀积后缀积，看了题解后发现状态不必那么冗杂，直接考虑和谁相通即可。
W Intervals
什么，居然是 NOIP2023 T4！其实并不是很像，原题其实是 CF115E
设 \(f_i\) 表示最后一个 \(1\) 放在 \(i\) 时的方案数，此时有一个 \(n^2\) 做法，直接考虑和前面的 \(1\) 接上后产生的新贡献，这样是正向考虑，不如我们不改变贡献，而去改变之前的 DP 值，达到贡献抵消的效果，所以把 \(f\) 拍到线段树上，线段树维护的时在当前位置时，\(f\) 减去重复区间后的贡献，每次逃离一个区间后，给对应区间加上价值即可，线段树空间没开四倍调 20 分钟。
X Tower
如果我们知道了箱子的堆叠顺序，那么这就是一个背包问题。所以考虑如何确定背包顺序，经典贪心套路 Exchange Arguments，考虑对于两个物品，如果 A 放在上面后承重能力比 B 放在上面后承重能力大，那么就让 A 在上面，这种贪心方法往往要求元素之间的关系有传递性和交换性。根据这个规则排序后就可以使整个顺序最优，然后背包即可。
Y Grid 2
这题大家应该都做过。首先根据卡特兰数可以算出一点到另一点中间没有阻碍的方案数，由于阻碍很少，正难则反，考虑计算至少经过一个阻碍的方案数，设 \(f_i\) 表示从起点出发，到达第 \(i\) 个障碍且中间不经过其他障碍的方案数，转移就直接把之前的障碍抠掉即可，因为都是第一次到达，所以不重不漏。
Z Frog 3
斜率优化板子。
标签：AtCoder,匹配,速通,方案,这题,即可,考虑,DP From： https://www.cnblogs.com/Ishar-zdl/p/18496055