多发现题目的性质，从性质上下手
dp转移可以通过更改顺序来消除一些限制
把dp转移需要的条件写进dp状态里
dp的用途是广泛的，包括计数、最优化、可行性等等，其根本就是利用记忆化避免重复计算
-
看到奇怪的限制应该考虑将其形式化，常规化
-
看到位运算类的性质可以考虑数位
dp -
一个排列的笛卡尔树唯一，因此关于排列的若干个区间最值限制可以考虑计算笛卡尔树的形态
CF1580B Mathematics Curriculum -
如果元素的贡献与区间最小最大值有关，那么考虑使用
min-max分治，使每个元素在其左右端点不在同一块的地方被统计，min-max分治不仅可以计数，也可以求最优化
P3592 [POI2015] MYJ 【最优化dp】
CF549F Yura and Developers 【计数】 -
阶梯型DP优化&pht转化的巧妙运用
P6944 [ICPC2018 WF]Gem Island -
看到要求商最大可以先从
0/1分数规划开始想，0/1分数规划不一定仅限于每一个物品才会带来贡献
P3778 [APIO2017]商旅 -
dp的用途很广，甚至可以用来防止重复比较等，看到题目不会做先想dp
P6764 [APIO2020]粉刷墙壁 -
DP具有无后效性的体现：构成DP的每一步决策都只与当前的状态有关，不与前后有关，就比如说给一堆限制，然后可以将这堆限制分类，然后每一类DP，保证在符合之前所有类的限制的情况下满足当前这一类的限制，可以看做是一种分部处理“且”限制的手段
P5369 [PKUSC2018]最大前缀和 -
考虑生成一个排列的办法：状压目前使用了多少位，枚举下一步拓展谁
-
树形结构很常见，可以用来dp
SP3734 PERIODNI - Periodni -
对于树上任意非祖先两点的都会对其
lca产生限制，就直接按照dfs下去即可，设计状态的时候直接就是f[i]表示以i为根的子树中，本身已经满足限制的状态，合并的时候考虑不同子树对于根的限制即可 -
最优化dp转移的决策（转移路径）不一定要存在直接转移，只需要保证存在最优（复合）路径就够了，就是冗余转移优化
P4762 [CERC2014]Virus synthesis -
如果若干个集合两两之间的关系要么包含要么不交，那么集合的包含关系可以构成一棵树
CF494C Helping People
P8252 [NOI Online 2022 提高组] 讨论 【神仙lsy的集合划分树】 -
计数题要考虑如何把问题分组，做到不重不漏，比如可以考虑以最大编号或者最原始祖先来区分等等，就是类似于至少=恰好\(\times\)至少这种，反正选出来的代表要具有 唯一代表性 ，即可以唯一代表一类情况，且分类重不漏
P7105 「C.E.L.U-01」门禁 【差一点想出来的题】
CF512D Fox And Travelling【自己想出来的题】 -
权值是乘在一起然后开根的，可以把开根看做在指数上除，然后就变成分数规划问题
-
dp的有效状态实际上是很少的，可以利用上
CF1584F Strange LCS -
如果一些情况使得某一位非常小，某一维非常大（只能接受log），那么可以考虑矩阵乘法
-
01背包的合并具有决策单调性
-
有些题目不能完全预处理，那么就可以先预处理出能预处理的，然后把不能直接预处理出来的用已经预处理的算出来，差不多就是部分预处理
P4133 [BJOI2012]最多的方案 -
计数类问题考虑加乘法原理
P5664 [CSP-S2019] Emiya 家今天的饭 -
背包问题决策具有无向性
P4095[HEOI2013]Eden 的新背包问题
正着做一次，倒着做一次，之后因为无向性就可以把正着做和倒着做的结果合并！！
-
背包问题中交换物品的顺序对结果不影响
P4141 消失之物 -
对于要求元素不重复的dp，设计状态时可以考虑一个一个的插入元素，过程类似背包
-
计数dp在设计状态的过程其实是在把情况分类的过程，要注意分类的情况之间相互不包含或重叠，以免在统计时把部分情况算重
-
在让gcd最大的问题里的一种dp的阶段性：把最大的质数作为阶段来拓展
-
多个模式串匹配且长度不定的dp可以把模式串放到AC自动机上，接着dp状态就转变成匹配到AC自动机上的某个点时的状态
-
对于dp中的序列问题，如果每个元素的贡献只与其相对的大小关系有关，那么可以把元素换成康托序，同时一个排列与康托序是一一对应的
CF1542E1 Abnormal Permutation Pairs (easy version)