动态规划

动态规划方法通常用来求解最优化问题。具备两个要素：
1.最优子结构：一个问题的最优解包含其子问题的最优解。求解一个子问题时用到了某些资源，导致这些资源在求解其他子问题时不可用。
2.重叠子问题：问题的递归算法会反复求解相同的子问题，而不是一直生成新的子问题。

动态规划方法步骤描述：

1.刻画一个最优解的结构特征
2.递归地定义最优解的值
3.计算最优解的值，通常采用自底向上的方法
4.利用计算出的信息构造一个最优解

动态规划实现方法：

1.带备忘的自顶向下法：按照自然地递归形式编写过程，但过程会保存每个子问题的解。当需要子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；否则，按通常计算方式计算这个子问题。
2.自底向上法：这种方法一般需要恰当的定义子问题规模的概念，使得任何子问题的求解都只依赖于更小的子问题的求解。因而我们可以将子问题按规模排序，按有小到大的顺序求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果以保存。
如果每个问题都必须至少球结一次，自底向上动态规划算法会比自顶向下备忘算法快。因为自底向上算法没有递归调用的开销，表的维护开销也更小。如果子问题空间中的某些子问题完全不必求解，被忘方法优势，只会求解哪些必要的子问题。

状态转移表法：

先画出一个状态表。状态表一般都是二维的，所以你可以把它想象成二维数组。其中，每个状态包含三个变量，行、列、数组值。我们根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，我们将这个递推填表的过程，翻译成代码，就是动态规划代码了。

状态转移方程法:

状态转移方程法有点类似递归的解题思路。需要分析，某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程.