在前两集漫画中，我们通过一个算法问题的完整解题过程，讲述了动态规划的基本概念和思想。没看过前两集的朋友可以点击下面的链接：

漫画说算法–动态规划算法一（绝对通俗易懂，非常棒）
漫画说算法–动态规划算法二（绝对通俗易懂，非常棒）

在第二集的末尾，给出了一道动态规划的进阶题目——国王和金矿。让我们先来回顾一下问题：

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

下面，继续我们的故事。

————————————

## 方法一：排列组合

每一座金矿都有挖与不挖两种选择，如果有N座金矿，排列组合起来就有2^N种选择。对所有可能性做遍历，排除那些使用工人数超过10的选择，在剩下的选择里找出获得金币数最多的选择。

代码比较简单就不展示了，时间复杂度也很明显，就是O(2^N)。

F(n,w) = F(n-1,w) (n>1, w<p[n-1]) F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w>=p[n-1])

其中第三条是补充上去的，原因不难理解。

## 方法二：简单递归

把状态转移方程式翻译成递归程序，递归的结束的条件就是方程式当中的边界。因为每个状态有两个最优子结构，所以递归的执行流程类似于一颗高度为N的二叉树。

方法的时间复杂度是O(2^N)。

## 方法三：备忘录算法

在简单递归的基础上增加一个HashMap备忘录，用来存储中间结果。HashMap的Key是一个包含金矿数N和工人数W的对象，Value是最优选择获得的黄金数。

方法的时间复杂度和空间复杂度相同，都等同于备忘录中不同Key的数量。

## 方法四：动态规划

方法利用两层迭代，来逐步推导出最终结果。在外层的每一次迭代，也就是对表格每一行的迭代过程中，都会保留上一行的结果数组 preResults，并循环计算当前行的结果数组results。

方法的时间复杂度是 O(n * w)，空间复杂度是(w)。需要注意的是，当金矿只有5座的时候，动态规划的性能优势还没有体现出来。当金矿有10座，甚至更多的时候，动态规划就明显具备了优势。

首先,我们看一下官方定义:定义: 动态规划算法 是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者 说 分治）的方式去解决。 动态规划算法 的基本思想与分治 法 类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。基本思想与策略编辑: 1） 动态规划 （Dynamic Programming） 算法 的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理 算法 2） 动态规划算法 与分治 算法 类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 3）与分治 法 不同的是，适合于用 动态规划 求解的问题，经分解得到的子问题往往不是互相独立的。（即下一个子阶段的求解是建立在上一个子阶段的解的基础上， 进行进一步的求解） 4） 动态规划 可以通过填表的方式来逐步推进，得到最优解。