动态规划（Dynamic Programming）

动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。 区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。 其实就是说，动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决从而得到更小的运行时间。 即用动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。

将 动态规划 的概念关键点抽离出来描述就是这样的：

• 动态规划法试图只解决每个子问题一次。

• 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

爬楼梯问题

下面通过爬楼梯问题来分析使用动态规划的解决问题（该问题也是在现场面试中遇到的）。

问题描述：爬楼梯，我们每次可以走 1 级阶梯或者 2 级阶梯，那我们走 50（n） 级阶梯总共有多少种走法。 在现场思考过程中，如果没有使用动态规划的话，那就要用递归的概念去做。

递归方式

我们在高中的数学课里面应该学习过规律推理，那我们可以很容易的去推理出来公式： 1 级台阶： 1 种走法（f(1)） 2 级台阶： 2 种走法（f(2)） 3 级台阶： 3 种走法（f(3) = f(2) + f(1)） 4 级台阶： 5 种走法（f(4) = f(3) + f(2)） 5 级台阶： 8 种走法（f(5) = f(4) + f(3)） ... n 级台阶： f(n) = f(n-1) + f(n-2) （n > 2）

通过以上公式，很容易推导出一下递归代码：

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

code:

int f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    // a 保存倒数第二个子状态数据，b 保存倒数第一个子状态数据， temp 保存当前状态的数据
    int a = 1, b = 2;
    int temp = a + b;
    for (int i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp; 
    }
    return temp; 
}

从递归到动态规划

还是以爬台阶为例，如果以递归的方式解决的话，那么这种方法的时间复杂度为O(2^n)

详解动态规划

动态规划中包含三个重要的概念：

• 最优子结构

• 边界

• 状态转移公式

在爬台阶问题中：

f(10) = f(9) + f(8) 是最优子结构 f(1) 与 f(2) 是边界 f(n) = f(n-1) + f(n-2) 状态转移公式

爬台阶问题只是动态规划中相对简单的问题，因为它只有一个变化维度，如果涉及多个维度的话，那么问题就变得复杂多了。

难点就在于找出动态规划中的这三个概念。感觉跟我们高中学习的推理证明题有点像，通过现在的条件推断出结果。

国王和金矿问题

问题描述

有一个国家发现了 5 座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是 10 人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？