理论基础
动态规划的特征
问题能抽象成多阶段决策最优解模型。有三个特征：
最优子结构
问题的最优解包含子问题的最优解。可以通过子问题的最优解，推导出问题的最优解。
无后效性
推导后面阶段的状态时，只关心前面阶段的状态值，不关心具体过程；某阶段状态确定后，就不受之后阶段的决策影响。
重复子问题
不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。
求解方法
状态转移表
状态转移表一般是二维的，每个状态包含行、列、数组值三个变量，根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。
大致思路可以概括为：
回溯算法实现->定义状态->画递归树->找重复子问题->画状态转移表->根据递推关系填表->翻译成代码
状态转移方程
根据最优子结构，写出递归公式，也就是状态转移方程。
大致思路可以概括为：
找最优子结构->写状态转移方程->翻译成代码
常见算法比较
贪心、回溯、动态规划可以归为一类，都可以抽象成多阶段决策最优解模型。而分治算法解决的问题也是最优解问题，但往往不是多阶段决策模型。
回溯算法相当于穷举搜索，时间复杂度是指数级别。
分治算法分割成的子问题不能重复，而回溯算法存在大量重复子问题，动态规划就是解决重复子问题。
贪心算法是动态规划的特殊情况，他的第三个特征不是重复子问题而是贪心选择性，通过局部最优的选择产生全局的最优选择，每一阶段都选择当前最优的决策从而构成全局最优解。
参考链接
