动态规划 总结
一、动态规划特点。
- 求解目标具有最优解。
- 目标问题的最优解可以分解为各个子问题的最优解。
- 大问题分解为若干小问题后，这些小问题之间还有相互重叠的更小的子问题。
- 从上往下分析问题，从下往上求解问题。
PS：总结于 《剑指offer》author：何海涛
二、动态规划条件。
- 优化子结构。即一个问题的优化解包含子问题的优化解。作用：可以缩小子问题集合；保证了可以从下而上求解问题呢
- 重叠子问题。子问题解可以多次使用。作用：加速求解。保证有效性
- 子问题空间小。
三、动态规划的设计步骤
- 分析优化解结构。看是否能有动态规划（依据其条件）
- 递归定义最优解的代价。描述这个问题最优解与子问题最优解的关系。
- 自下而上计算优化解的代价并保存，并获得构造最优解的信息。
- 根据保存信息构造优化解。
四、动态规划例子。
1.分析优化解结构。看是否有优化子结构。
2.分析重叠子问题。（举例子看看）
3.递归定义最优解代价。
4.设计数据结构（足以容纳所需要的解）
填充方法：（从对角线开始像目标推进）
伪代码：
输出：