为什叫做“动态规划”

我想你应该在高中接触过线性规划了，动态规划看起来和他差不多。“规划”这个字来自运筹学中的规划论，除了刚才提到的还有非线性规划、整数规划、组合规划、随机规划、多目标规划等。他们都是寻找一个最优解的方法。

我们也知道分治法，通过将一个问题拆分成若干子问题来求解，但是如果我们的子问题之间有重叠部分的话，分治法就会多次计算重叠部分，所以我们将重叠部分单独计算并保存在一个数组里，减少重复工作，这就是动态规划的基本思想。

何时使用动态规划

最优子结构：问题的一个最优解包含了子问题的最优解 子结构重叠：子问题的求解方式相同——可以递归求解

设计一个动态规划算法

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

数字三角形

在下面的数字三角形中寻找一条从顶部到底边的路径，求出所经过数字的最大和（路径上的每一步都只能往左下或右下走）。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

参考文章 北京大学 算法基础 Lecture 10 - 数字三角形