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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://tommyyang.gitbook.io/javainterview/codeinterview/dynamic-programming.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.