动态规划
阶段
阶段是指，在问题解决过程中，同一时刻可能出现的不同状态的集合。
阶段与贪心
若一个问题有n个阶段，每个阶段有多个状态，每个阶段都可以得到下个阶段中的若干个，则遍历最终阶段的状态必须要遍历之前每个阶段的某些状态。
如果下一步最优可以从当前最优得到，不断递推下一个状态即可，此类问题为贪心，计算方法是递推。
如果下一步最优与前两阶段有关，则没有本质区别，与之相对的，下一步最优可能与所有阶段有关。
部分此类复杂问题的快速求解在于无后效性。
动态规划
最优化原理
是解决多阶段决策问题的理论，其原始表示（bellman）是：
一个过程的最优策略有这样的性质，即无论其初始状态及初始决策如何，其以后诸决策对第一个决策形成的状态作为初始状态的过程而言，必须构成最优策略。
其实质是：多阶段决策过程有这样的性质：不管过去的过程如何，只从当前状态和系统最优化要求出发，做出下一步最优策略。
换言之：一个最优决策的子决策，只考虑其初态和终态，也必须是最优策略。
无后效性
无后效性是指如果在某个阶段上过程的状态已知，则从此阶段以后过程的发展变化仅与此阶段的状态有关，而与过程在此阶段以前的阶段所经历过的状态无关。利用动态规划方法求解多阶段决策过程问题，过程的状态必须具备无后效性。
DP的使用
在LIS例子中，因为有无后效性，即不需要关心以前是哪些，只知道长度和最后一个字母即可，或者说，最后一个阶段的状态能部分描述（与问题相关的）信息，且LIS问题满足最优化原理，所以可以用DP求解。
阶段与问题求解
每个阶段只有一个状态：递推
每个阶段的最优状态都是上一个阶段的最优状态的到：贪心
每个阶段的最优状态是之前所有状态的组合：搜索
么个阶段的最优状态可以从之前某个阶段的某个或者某些状态直接得到而不用管这个状态如何得到：动态规划
DP与分治
分治中将大问题拆分为许多小问题解决，对于有的问题，分治过程中产生了大量重复的小问题，这导致了直接分治的指数复杂度，而DP就是将这些重复的小问题的结果记录下来。
从而减少对状态空间的重复遍历，实现高效遍历。
DP与搜索
一切拓扑有序图结构的搜索都可以改写为DP,DP是高效率的，因为不会遍历到重复状态，但是很多问题中，搜索更加实用。
搜索是自顶向下的，可以进行剪枝，从而去除大量的无效遍历，但是经常重复遍历。
DP是自底向上的，可以避免重复遍历，但是会进入无效分支。
所以二者在不同方面有优势，在不同问题中各有有点，而对搜索的一种常见优化：记忆化，可以对搜索的缺点进行优化，是一种十分实用的手段。
（DP貌似无法剪枝？）
DP的局限
DP主要有三个缺点：
无定式
DP问题求解没有同一范式，复杂数学问题转化并不轻松
问题限制
DP要求的最优化原理和无后效性都是很强的条件，其中最优化原理是由问题本身确定，无法改变，无后效性可以通过增加DP的维度（状态变量数）满足，不过受第三个限制影响：
维度
DP一般只能有123维，高维DP复杂度过大，没有意义。
动态规划的模式性
一般分为如下阶段：
- 划分：将问题分为若干有序阶段
- 选择：选择一种状态变量表出状态
- 决策与状态转移：如何从上一状态与决策来到现状态，并决策（一般是在当前状态决上一步的策）
- 规划方程和边界