今天是暑假留校第一天，准备先复健一下。
最近几个月有点摸鱼，打算把动态规划，基本数据结构（线段树，树状数组）给先整一整，然后就是之前分的图论方向，需要把几个重要的（最短路系列，tarjin，连通性相关，图的匹配，网络流）再做些题。
今天的话就是先动态规划。
1、记忆化搜索
特征总结：
①不依赖任何外部变量。可以通过有外部变量的优化过来。
②答案以返回值的形式存在，不能以参数的形式存在。
③对于同一组参数，其对应的答案是一致的，这也是能记忆化搜索的原因。
写这种题首先可以写出他的暴搜程序，改成不需要任何外部变量，添加记忆化数组。
2、区间dp
特征总结：能将问题分解为能两两合并的形式。
对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。
3、DAG上的dp
特征总结：这类dp可以先由题目中的二元关系建立一个有向无环图模型，再在这个DAG上进行dp。有点类似于记忆化搜索。
4、树形dp
特征总结：可以建立树形结构，并可以用所有叶子节点的方案去更新其父节点的最优解。
一般都是采用递归，遍历子节点直至叶子节点回溯更新答案。
换根dp
特征总结：通常需要两次 DFS，第一次 DFS 预处理如深度，点权和之类的信息，在第二次 DFS 开始运行换根动态规划。
