1、动态规划与分治法的区别：
都利用递归，但分治法的子问题不重复，动规的子问题重复，因此需要表格保存子问题的解，以避免重新计算。

2、动态规划应用方向（能应用该方法解题的问题特征）：

动态规划用于解决最优化问题。当问题描述中出现“···使得···最好、最优”时，可以思考利用动态规划方法解题。

3、动态规划方法介绍：
动态规划是付出额外的内存空间来节省时间，典型的时空平衡。
3.1、动态规划算法设计步骤：

最优子结构：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

3.2、动态规划算法实现方法：
a）带备忘的自顶向下法：
按正常递归过程进行编写，但过程中保存每一个子问题的解。求解子问题时，先查找是否已保存过此解，是则返回，否则计算后保存返回。
钢条切割问题伪代码：

b）自底向上法：
先解决最小规模子问题的解，然后问题逐步扩大，当扩大到待求解问题时，其前提子问题都求解完毕(将子问题按规模排序，按由小到大进行求解)。
由于没有频繁的递归调用开销，自底向上法的时间复杂度具有更小的系数。
钢条切割问题伪代码：

两层循环： 一层循环用于遍历小问题–>大问题；第二层用于求解该小问题。

c）完整代码：返回最优解的值r与最优解s：


参考资料： 算法导论359页，15章动态规划

总结：

1、动态规划用空间换时间，需要开辟一个数组用于保存子问题的解，避免子问题的重复计算。
2、动态规划用于求解最优化问题，常用自底向上方法（先求解子问题，再逐步扩大。从小问题到大问题，常利用for循环遍历）。