DP小结

DP种类

• 线性DP
• 区间DP
• 树形DP
• 背包DP
  • 01背包
  • 满背包
  • 完全背包（转成01背包）

例子：
线性动规:拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等;
区域动规:石子合并， 加分二叉树，统计单词个数，炮兵布阵等;
树形动规:贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等;
背包问题:01背包问题，完全背包问题，多重背包问题，分组背包问题，二维背包，装箱问题等;

关键

无后效性我们要求状态具有下面的性质:如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。

状态

决策一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。

阶段把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同.描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的。此外，也有阶段变量是连续的情形。

优化

方向：减少状态量，减少状态转移时间，改变状态表示
滚动数组
递归->递推
多叉树转二叉树
左儿子，右兄弟
转化后由左上到右下相当于原来的一层

示例.JPG