主要内容 #

1. 动态规划的概念
2. 举例说明

1. 动态规划的概念 #

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。
动态规划方法通常用来求解最优化问题(optimization problem)。这类问题通常有很多可行的解，每一个解都有一个值，我们希望寻找具有最优值的解。我们称这样一个解为问题的一个最优解，而不是唯一的最优解，因为可能有多个解都达到最优值。
通常我们通过如下四个步骤设计一个动态规划算法：

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

步骤1～3是动态规划算法求解问题的基础，如果我们仅仅需要一个最优解的值，而不是解本身就可以忽略步骤4，有时就需要在执行步骤3的过程中去维护一些额外的信息，以便用来构造一个最优解。

2. 举例说明 #

给定一个r行的数字三角形（r <= 1000），需要找到一条从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到当前点左下方的点或右下方的点。

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

在上面这个例子中，最优路径是7->3->8->7->5。
最简单粗暴的思路是尝试所有的路径。因为路径条数是 O(2^r)级别的，这样的做法无法接受。
注意到这样一个事实，一条最优的路径，它的每一步决策都是最优的。
以例题里提到的最优路径为例，只考虑前四步7->3->8->7 ，不存在一条从最顶端到4行第2个数的权值更大的路径。
而对于每一个点，它的下一步决策只有两种：往左下角或者往右下角（如果存在）。因此只需要记录当前点的最大权值，用这个最大权值执行下一步决策，来更新后续点的最大权值。
这样做还有一个好处：我们成功缩小了问题的规模，将一个问题分成了多个规模更小的问题。要想得到从顶端到第r行的最优方案，只需要知道从顶端到第r-1行的最优方案的信息就可以了。
这时候还存在一个问题：子问题间重叠的部分会有很多，同一个子问题可能会被重复访问多次，效率还是不高。解决这个问题的方法是把每个子问题的解存储下来，通过记忆化的方式限制访问顺序，确保每个子问题只被访问一次。