文档介绍：[][Library]Summary 动态规划总结 by Amber
1
动态规划总结
by Amber
按状态类型分
写在前面：
从状态类型分，并不表示一题只从属于一类。其实一类只是一种状态的表示方法。s)

Stone Pile(ural1005 Stone Pile)
公路巡逻(CTSC2000)

共性总结
动态规划的顺序
一般按照后序遍历的顺序，即处理完儿子再处理当前节点，才符合树的子结构的性质。
多叉树转换为二叉树
由于要分配附加维到各个节点，而分配附加维是个划分问题，若还是按当前节点到各个儿子节点分配，则成了一个整数划分问题,O(n2)。所以要把多叉树转换为二叉树，这样才能按动态规划的方式只决策当前点的分配问题, O(n)。
加当前点的选或不选的常数维
加此维解决的是后效性问题。
……………………
在将边信息转成树时的技巧
将读入的边分裂成2条边，将这2条边关联起来（就是找到一条边，另一条边的编号就知道）。用前向星表示法表示边（按起点有序），以后用边的时候，用了一条边打不可用标志，也将关联边打不可用标志。这样可以保证O(n)的时间完成信息处理，而且在父节点找儿子的过程中带来很大的方便。
复杂度
树型动态规划复杂度基本上是O(n)；若有附加维m，则是O(nm)。
题库
选课(CTSC97-3)
由于要分配课程数，所以要多叉树转换为二叉树。
贪吃的九头龙(NOI02-3)
若小头数大于1的话，则让不同的小头吃一段树枝的2个端点。
这样就把问题转化成：附加维是大头吃的个数，当前点由不由大头吃的常数维的动态规划。由于涉及划分问题，所以要多叉树转换为二叉树。
求树的质心(sgu134 Centroid)
给出一棵边不带权的树，求点,使得去掉此点后,剩下的最大的连通子图的顶点数最小.
求树中的点最远距离最近。
给出一棵边带权的树，求树中的点，使得此点到树中的其他结点的最远距离最近。
Computer Network (sgu149)
Computer Net (ural1056)
[][Library]Summary 动态规划总结 by Amber
4

集合动态规划（状态压缩）
共性总结
数据特殊性
给出的数据在某一个或几个维度上一般具有比较小的范围（可以枚举一类的状态）。
一个枚举的状态是一个集合。
编码
由于集合中元素个数的不定性或范围大，直接开数组存，不好索引数组（编程复杂度太高），所以要将集合编码。
利用数据的可枚举性，将枚举的状态(集合)编码。一般来说码值的范围要很小（尽量排除无用的码值，如炮兵：当前格和上格存在炮兵的情况是非法的，可以排除）。
规定编码的码值代表的意思，要尽量规定好维护的码值。（如炮兵：当前格存在炮兵的用2，上格存在炮兵用1。这样下一层的规划时，只要码值-1即可）。
有时候可以直接利用编码的顺序动态规划，因为这时编码已经是拓补有序。如TSP问题当前已选点集合的状态的前驱的编码的值一定比当前的编码的值小。
状态压缩
对有限阶段的放置情况，行走情况编码（其实质也是放置的集合或行走路线的集合），这样的编码，也有人谓之