> For the complete documentation index, see [llms.txt](https://tommyyang.gitbook.io/javainterview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tommyyang.gitbook.io/javainterview/codeinterview/dynamic-programming.md).

# 动态规划（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）**

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

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

code:

```java
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 人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？