动态规划通常用来求解最优化问题，即有多个解都能到达最优值。
基本步骤
- 刻画最优解的结构特征
- 递归的定义最优解的值
- 计算最优解的值，一般用自底向上的求解方法
- 利用计算出的信息构造最优解（可忽略）
基本原理
最优子结构——刻画最优解的结构特征
如果一个问题的最优解包含子问题的最优解，此问题就具有最优子结构。某个问题是否能用动态规划，可以先考察它是否具有最优子结构，而后考察一下使用动态规划时，最优解是否用到了所有子问题的最优解。如钢条切割问题，问题的最优解是由切割后的两条钢条的最优解给出的。
发掘最优子结构的通用模式
- 证明问题的最优解的第一个组成部分是做出一个选择。这次选择会产生一个或多个待解的子问题。
- 在一个问题进行第一步选择时，假定已知哪种选择可以得到最优解，只是假定。
- 在假定完最优解的选择后，确定产生的子问题，以及如何去最好刻画子问题空间（有点不明白）。
- 利用cut-and-paste证明：作为原问题的最优解的组成部分，每个子问题的解就是它本身的最优解。（人晕了，好像有点懂）
如何去最好的刻画一个子问题空间：保持子问题空间尽可能的简单。
考虑一下：有向无权图的简单路径：最短简单路径、最长简单路径都具有最优子结构吗？
重叠子问题
适合动态规划求解的问题，除了具有最优子结构这个特性外，还应该具有重叠子问题：递归算法反复求解相同的子问题。即子问题空间足够小，使得每一次的递归算法总是会去求解相同的子问题。？
注意：最优子结构要求的是子问题的有关性，即其解也是原问题的解，而重叠子问题要求的是子问题的重叠性，同一个子问题会反复出现，动态规划只会去求解一次这样的重叠子问题。
重构最优解——构造最优解
通常把子问题所做的选择存在一个表中。根据表构造最优解。
自底向上的求解方法
自顶向下的求解方法
这是对递归法的一种改进，即对递归算法加入备忘(Memo)机制。
CutRod是没有掌握动态规划的时候写的，也是练手题，所以并没有按照基本步骤去解