今天学习一些基本DP
- 线性DP
- 区间DP
- 状压DP
- 树形DP
- 数位DP
不好定转移顺序就用记忆化搜索。
线性DP一般定义形如\(dp_{i,s}\)的状态，表示考虑了前\(i\)个，限制为\(s\)的最优解。视情况可以把\(i\)压掉，或者把\(s\)在枚举中体现以此压掉。
区间DP是从小区间合并到大区间，注意转移顺序，先要确定区间大小，然后枚举区间的位置，最后枚举区间中的断点来转移。二维的区间DP类似，都要先确定区间大小。
状压DP可以观察到数据范围较小，并且状态可以用01串表示。就是用01串表示状态，其他步骤与其他DP类似。
树形DP一般定义形如\(dp_{u,s}\)的状态，表示在\(u\)的子树内限制为\(s\)的最优解。树有很好的递归性质，利用递归进行DP。其中的换根DP要关注换根后答案的变化量。
数位DP可以记忆化搜索也可以递推着写，设状态要关注是否抵达上界且满足某种限制，一般问题具有可减性，转化为前缀和之差。
标签：总结,状态,26,01,2024.7,枚举,区间,DP From： https://www.cnblogs.com/EmilyDavid/p/18326436