- to update，还没有排版，lyd的这个部分还没看完
- 适用范围
a) 很多意想不到的问题可以用动态规划做
b) usu子问题重叠导致了解题的高效。
c) 最优解，方案数，甚至可行（bool，usu可以被其它而代替） - 设计：
a) 时间轴常常构成了阶段。（自然的正确性证明，阶段线性增长）
b) 把后效性记录下来
c) 不好列状态方程的时候，适当放缩定义。
d) 设初值，想好0 or (-)inf - 顺序：
a) 按阶段划分递推（保证子问题已经得到求解）
i. 阶段 状态 决策
b) 记忆化搜索 - 设计优化（usu体现在时间复杂度上）：
a) 预处理（数据很小甚至可以O(N^2)），esp倍增
b) 放缩
c) 贪心思想强行要求顺序
d) 关注决策集合，eps最值，降一维。边扫边处理 - 空间优化：
a) 滚动数组
b) 不要第一维
c) NOTICE:
i. 状态之间的循环顺序
ii. 输出方案时省不略。（usu记录某一个状态是怎么转移而来的，开与状态等大的来源记录数组） - 环形处理
a) 拆开复制
b) 两次dp，分类讨论。一次拆开，另一次通过适当赋值和条件设计出强制相连但与环等价的算法
常见模板：
- 背包（很多问题都可以转化成背包）
a) 0/1
b) 完全（inf物品）
c) 多重（finite物品）
i. 二进制拆分 or 单调队列优化 咕
d) 分组 - 区间
- 树形（以其为根的子树的信息）
a) 通常的代码实现
i. 先init本节点的信息
ii. 递归，usu回溯时合并信息
b) 不定根的树形dp：二次扫描 换根
i. 第一次扫描：任选一个根，对答案树形dp（usu回溯时状态转移）
ii. 第二次扫描：之前那个根的信息应该已完毕，自上而下统计其他节点的答案 - 有后效性（方程为环）（高斯消元）咕
