动态规划基本要素

动态规划性质： 1  最优子结构性质  2 子问题重叠性质 ----->该问题可用动态规划算法求解的基本要素

1 最优子结构

当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。最优子结构性质提供了该问题的可用动态规划算法求解的重要线索。

动态规划，利用问题的最优子结构性质，以自底向上的方式递归的从子问题的最优解逐步构造出整个问题的最优解。

2 重叠子问题

动态规划，避开了递归时，重复的计算相同子问题的过程，对每个子问题只解一次，而后将其保存在一个表格中，当再次需要的时候，只是简单的用常数时间查看一下结果。

3 备忘录方法

递归方式自顶向下

首先，查看其相应的记录项，若存在，直接返回。若不存在，则保存，以备以后继续查看。