入门级-线性动态规划-入门

# 动态规划入门

---

### 1、什么是动态规划

动态规划是一种数学方法，一般应用于多决策过程，用来求最优化的问题。

动态规划通过定义问题的状态以及状态之间的关系，来拆分问题，使得问题能够以递推的方式被解决。

如何观察问题，定义问题的状态，从而对问题进行拆分，这是动态规划的关键之处。

另一方面，对于一个问题，以什么作为状态，并不固定，需要有丰富的经验、很强的观察能力和分析能力。这也是大家觉得动态规划比较难掌握的地方。

---

### 2、动态规划怎么用

#### 2.1 定义状态

问题：最长递增子序列的长度

求一个数列的最长上升递增子序列（LIS）的长度。

例如：1 7 2 8 3 4，

递增子序列有：1 7, 1 8, 1 7 8, 1 2 3 4,  2 3 4等等

最长递增子序列为 1 2 3 4， 长度为4

第二长的子序列有：1 2 3 、 1 7 8等，长度为3

问题是什么？子问题又是什么呢？怎么叫通过定义状态来拆分问题？

---

我们将问题换一种说法：

设 $F_k$ 为数列中第 $k$ 项元素为结尾元素的最长递增子序列的长度

求 $F_1...F_n$ 的最大值

例如 $F_5$ 为 `1 7 2 8 3` 的最长递增子序列的长度，结果为3

$F_4$ 为 `1 7 2 8` 的最长递增子序列的长度，也是3

这个问题与原问题等价，但这么描述就可以拆分问题。

对于 $F_k$ 来说，$F_1...F_{k-1} $ 都是 $F_k$ 的子问题：因为，以第 $k$ 项结尾的`LIS` 包含着以第 $1...k$ 项中某项结尾的 `LIS`。

描述“设 $F_k$ 为....”，就叫做对状态的定义，$F_k$ 叫做状态，对应的 $k$ 是我们提取的维度。

之所以叫状态而不是叫问题，一是避免与原问题混淆，二是因为这是一个数学定义。

---

### 2.2 状态转移方程

定义了状态，也即定义了问题与子问题，$F_1...F_{k-1}$ 都是 $F_k$ 的子问题。

接下来，就可以拆分问题，如何将 $F_k$ 拆分为子问题（的组合）呢？

实际就是找到状态与状态之间的关系式，让 $F_k$ 可以通过 $F_1...F_{k-1}$ 运算得到。

$F_1=1$（边界）

$F_k=\max\limits_{i = 1}^{k}{ F_i} +1, 1\le i \lt k且A_i \lt A_k$

以上，由于 $F_k$ 的结尾元素为$A_k$，则 $A_k$ 必须大于 $A_i$。

---

#### 2.3 构造最优解

由状态转移方程，就可以计算出所有的状态。

注意：状态并不一定是最终的最优解，有时候还要通过状态再进行计算，来构造出问题的最优解。

---

### 3、动态规划的实现

#### 3.1 图表实现

定义状态和状态转移方程以后，就可以根据状态画出图（或表格），然后按照拓扑排序依次更新每个状态的值。

---

例如：对于 `1 7 2 8 3 4`，找 `LIS`

| a[] |1    | 7    | 2    | 8    | 3    | 4    |
| ----|---- | ---- | ---- | ---- | ---- | ---- |
|Fi/dp[]|1| 2 |	2| 3 |	3| 4 |
|b[]|1|  | 1 |  | 3 | 5 |
(b[]表示记录是从前面哪个元素来的)

上图从左到右填充，例如：

- 首先填写F1，值为1
- 然后填写F2，F1+1 = 2
- F3，F1+1 = 2
- F4，max(F1,F2,F3)+1 = 3
- F5，max(F1,F3)+1 = 3
- F6，max(F1,F3,F5)+1 = 4

---

#### 3.2 递归编程

显然，可以用递归函数的方式来编写以上状态转移方程。

```c++
int f(int k) {
  if(k==1) return 1;
  //序列的数组从下标1开始
  int r=0;
  for(int i=1; i<k; i++) {
    if (a[i] < a[k]) r=max(r, f(i)+1);
  }
  return r;
}
```

---

需要注意的是，递归会产生大量的重复计算，例如：

- f(k) -> f(k-1)、f(k-2)...f(1)
- f(k-1) -> f(k-2)...f(1)
- ......

这是一个树，总共结点规模约为 $k^k$。

这样的运算量显然有问题，于是要把这些重复的计算存储起来，下次用到的时候重用。

---

#### 3.3 记忆递归

假设用一个状态数组dp[N]存储前面运算过的状态，则代码变成：

```c++
int dp[N];
int f(int k) {
  if(k==1) return 1;
  int r=0;
  for(int i=1; i<k; i++) {
    int tmp;
    if(dp[i]) tmp = dp[i];
    else tmp = dp[i] = f(i);

if (a[i] < a[k]) r=max(r, tmp+1);

}
  return r;
}
/*
f(1),f(2),...,f(n)
    f(n) (f(1)...f(n-1))
    dp[1]=1;
dp[2]=dp[1]+1;a[1]<a[2]
*/
```

---

#### 3.4 递推

用数组存储每次运算好的状态，然后依次往后递推。

```c++
int dp[N];
int f(int k) {
  dp[1] = 1;
  for(int i=2; i<=k; i++) {
    int m = 0;
    for(int j=1; j<i; j++) {
      if(a[i] > a[j]) m=max(m, dp[j]+1);
    }
    dp[i]=m;
  }
  return dp[k];
}
```

---

### 4、动态规划的特征

对问题进行分析，具备以下三个特性的，比较适合使用动态规划。

---

#### 4.1 最优子结构

问题的最优解就是找到此问题的最优状态。

"每个最优状态可以根据前面某个（或某些）状态直接得到"

这个性质就叫做“最优子结构”。

最优子结构表示问题（状态）的最优解包含其子问题（状态）的最优解。

---

#### 4.2 无后效性

"每个最优状态可以根据前面某个（或某些）状态直接得到"

“而不管之前这些状态是怎么得到的”

后面这个性质，称之为“无后效性”。

无后效性表示计算最优状态的时候，不需要关注前面的状态是怎么得到的（不受影响），只需要用到它们的值即可。

---

#### 4.3 子问题重叠

在状态转移方程计算的时候，有大量的子问题被重复运算。

动态规划要求所有的子问题都只需要解决依一次，存储起来供下次重用。

如果子问题重叠性不强，用动态规划的收益就不大，必要性就不强。

---

### 5、动态规划与其它算法的关系

首先，递推、递归是动态规划编程实现比较常用的技巧。

对于一个问题：

- 首选模拟、枚举、搜索
- 问题可分解成独立子问题的，用分治
- 最优状态可由上一个最优状态得到的，用贪心
- 最优状态可由前面某个(些)状态得到而不管之前状态是如何得到的，用动态规划

---

## 例题和练习

### 演示-爬楼梯

[CCFPB01E03  爬楼梯](http://39.99.183.126:8888/p/CCFPB01E03)

---

有一座高度是n级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。请问一共有多少种走法。

输入样例1：

```
10
```

输出样例1：

```
89
```

---

#### 二、分析

##### 1、模拟

- 从最下走到第一级台阶，有1种走法
- 从最下走到第二级台阶，有2种走法:
  - 走法一：先到第一级，再从第一级到第二级
  - 走法二：直接到第二级
- 从最下走到第三级台阶，有3种走法：
  - 走法一：先到第一级，再跨两级直接到第三级
  - 走法二：先经过第一级到第二级，再到第三级
  - 走法三：先到第二级，再跨一级到第三级

注意到第三级台阶的走法，可以描述成两种选择：

- 选择一：先到第一级，再跨2步到第三级，走法数是到第一级的走法数
- 选择二：先到第二级，再到1步第三级，走法数是到第二级的走法数

根据加法原理：

到第三级的走法数 = 到第一级的走法数 + 到第二级的走法数

---

##### 2、思路分析

根据以上模拟，抽象出一个概念：

对于任何一级台阶，假设级数为n，想要走到第n级，必须先走到第n-2级或者第n-1级，然后才能通过走1步或2步的方式走到第n级。

- 如果先到第n-2级，那么走法数就是到第n-2级的走法数
- 如果先到第n-1级，那么走法数就是到第n-1级的走法数
  分析：

---

将台阶的级数作为维度（下标）
从下网上走到第i级（维度）台阶的走法数，作为状态（用dp[i]表示)）
一般维度作为下标，定义一个状态，分析是否具有无后效性，然后找出状态转移方程。

无后效性：状态的转移与如何到达该状态无关，也即“未来与过去无关”。
例如：

从第一级走2步到第三级，这个转移与如何到达第一级无关。
从第二级走1步到第三级，这个转移也与如何到达第二级无关。
状态转移方程：

```
dp[1] = 1, dp[2] = 2
dp[i] = dp[i-2] + dp[i-1]， 对于i>2
```

将状态转移的方式画出一个图，就是一张有向无环图：
![image](http://39.99.183.126:8888/file/2/TurnPdNVLacl_cVFy6FPy.png)

动态规划本质上就可以理解成状态在有向无环图上的递推过程。

---

##### 3、实现方法

对于动态规划的实现，可以用递归，也可以用递推，可根据具体情况选用不同的方法。

需要注意的是，状态（值）的变化一定要遵循状态的拓扑序，以下两种都可以：

```c++
dp[i] = dp[i-2] + dp[i-1]
dp[i+1] += dp[i], dp[i+2] += dp[i]
```

本题分别用f1（递归）、f2（递归＋记忆）、f3（递推1）、f4（递推2）四个函数来实现求第n级的走法数。

---

##### 4、实现代码

```c++
#include <iostream>
using namespace std;

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

int dp[100];
int f2(int n) {
  if(n<=2) return n;
  if(dp[n]) return dp[n];
  return dp[n] = f2(n-1) + f2(n-2);
}

int f3(int n) {
  int a=1, b=2;
  for(int i=3; i<=n; i++) {
    int tmp = a+b;
    a = b;
    b = tmp;
  }
  return b;
}

int f4(int n) {
  dp[1]=1, dp[2]=1;
  for(int i=1; i<n; i++) {
    dp[i+1] += dp[i];
    dp[i+2] += dp[i];
  }
  return dp[n];
}

int main() {
  int n;
  cin>>n;
  //cout<<f1(n)<<endl;
  //cout<<f2(n)<<endl;
  //cout<<f3(n)<<endl;
  cout<<f4(n)<<endl;
  return 0;
}
```

---

## 练习

[WHOJ-P4442:使用最小花费爬楼梯](http://39.99.183.126:8888/p/4442)

---
### 最大递增子序列

给定一个长度为N的数列，求这个数列的最长递增子序列（LIS）的长度。

例如：1 7 2 8 3 4的LIS为1 2 3 4，长度为4

`输入样例：`第一行是n，第二行为n个数

```
6
1 7 2 8 3 4
```

输出样例：

```
4
```

输入样例2：

```
6
1 7 2 3 8 3
```

输出样例2：

```
4
```

数据规模：1<=N<1000

请使用动态规划实现。

---

#### 二、分析

理解问题，设计状态，找出状态转移方程。

维度：数列的下标
状态：设dp[k]为数列中第k项元素作为结尾的LIS的长度
状态转移方程：

```
dp[1] = 1
dp[k] = max(dp[i])+1, 1<=i<k 且a[i]<a[k]
```

---

解释：

dp[i]的结尾元素是a[i]，dp[k]的结尾元素为a[k]，即dp[k]是前面的某个dp[i]，加上a[k]形成的LIS的长度
找所有1<=i<k且a[i]<a[k]的i，求max(dp[i]+1)，即为dp[k]
最后输出的，是所有dp的最大值

---

请自己实现以下步骤：

1. 数据定义：N、a[N]、dp[N]
2. 输入n和a[n]
3. 递推计算dp
4. 输出

---

#### 四、扩展理解

如果定义状态：设dp[k]为前面k项的LIS的长度可以吗？

对于前面k项的LIS，可能会有多个结尾元素，有些大于a[k+1]，有些小于a[k+1]，会有后效性。

---

### 练习-信封错排

[信封错排](http://39.99.183.126:8888/p/2403)

n封信放入n个信封，要求全部放错，共有多少种放法。

请你用动态规划分析题目，设计状态，找出状态转移矩阵，然后编程实现。

输入样例：一个数字n

```
5
```

输出样例：错排的放法数目

```
44
```

数据范围：1<=N<=20

---

#### 二、分析

##### 1、理解题目

k封信放入k个信封，错排的放法数。

把信封理解成数组下标，信理解成数组的值，则问题转化为：

n个不相等元素的数组，每个位置都不等于其下标，有几种。

用什么做维度？k

状态是什么？dp[k]：k个元素的错排总数

状态方程是什么？

---

##### 2、状态转移方程

注意：以下的n不是题目输入的n，只是一个符号。

假设一种错排方案里，n位置放的是k元素，现在看k位置放的是什么值：

k位置放的是n元素，则除n、k位置之外的n-2个位置要全部错排，即dp[n-2]
k位置放的是m元素（不等于n），将n和k位置交换，则k位置放了k，n位置放了m，也就是除k以外的位置要全部错排，即dp[n-1]
根据加法原理，以上两种的和为 dp[n-1] + dp[n-2]

又，k元素的选值有n-1种，于是总的状态转移方程：

```
dp[n] = (n-1) * (dp[n-1] + dp[n-2])
```

---

##### 三、实验步骤

请自己实现以下步骤：

1. 接收输入n，定义dp数组
2. 递推实现动态规划
3. 输出

---

### 演示-最大子段和

---

#### 一、实验目标

[P204  【基础】最大部分和（连续部分和）](http://39.99.183.126:8888/p/204)

[洛谷1115](https://www.luogu.com.cn/problem/P1115)

给出一段序列，选出其中连续且非空的一段使得这段和最大。

输入样例：第一行n（长度），第二行n个数据

```
7
2 -4 3 -1 2 -4 3
```

输出样例：最大字段和，子段最小长度为1

```
4
```

样例说明：最大的字段和为4， 该字段为 3 -1 2

数据范围：

```
每个元素绝对值<= 10000
40%的数据：n<=2000
100%的数据：n<=200,000
```

本题要求用动态规划实现。

---

#### 二、分析

##### 1、理解题目

分析样例数据：

|下标|1|2|3|4|5|6|7|
|---|---|---|---|---|---|---|---|
|序列|2|-4|3|-1|2|-4|3|
|前缀和|2|-2|1|0|2|-2|1|
如果定义了前缀和$p[i] = a[1]+...+a[i]$，那么有子段和$s[i][j] = p[j] - p[i]$，表示下标为$i+1，\space ... \space，j$的子段和。

---

显然，如果p[j]固定的话，那么p[j] - p[i]最大，必然p[i]为最小。

于是定义状态：设dp[j]为前j个元素里最小的前缀和$p[i], 0\le i\le j$，

注意：序列从1开始，但前缀和0开始，令p[0] = 0

模拟如下：

|下标|0|1|2|3|4|5|6|7|
|---|---|---|---|---|---|---|---|---|
|序列|-|2|-4|3|-1|2|-4|3|
|前缀和|0|2|-2|1|0|2|-2|1|
|最小前缀和|0|0|-2|-2|-2|-2|-2|-2|
|最大字段和|0|2|0|3|2|4|0|3|

最大子段和为p[5] - dp[2] = 4，子段为3 -1 2

---

##### 2、状态设计

状态：设dp[j]为前j个元素里最小的前缀和p[i], 0<=i<=j，

状态转移方程为：

```
dp[0] = 0
dp[j] = min(dp[j-1], p[j])
```

最大字段和为max(p[j] - dp[j-1]), 1<=j<=n，

---

注意：

题目提示每个元素绝对值<=10000，也即max初始值为-10000
为什么减去dp[j-1]，因为题目要求最少要一个元素。
如果要找出序列，就要记录dp[j]在哪个下标

---

##### 3、换一种状态定义

定义状态：设dp[i]为第i个元素为结尾的最大子段和

那么对于dp[i]，要么是a[i]自己（从头计算），要么是dp[i-1]+a[i]

于是状态转移方程：

```
dp[1] = a[1]
dp[i] = max(a[i], dp[i-1]+a[i])
```

最后计算dp序列的最大值，即为总的最大子段和。

---

#### 三、实验步骤

请分别实现两种动态规划思路：

1. 数据定义和输入
2. 第一种思路f1()
3. 第二种思路f2()

---

#### 四、参考代码

```c++
#include <iostream>
using namespace std;

const int N=200005;
int n;
int a[N];
int p[N];
int dp[N];

void f1() {
  for(int i=1; i<=n; i++)
    p[i] = p[i-1] + a[i];
  
  for(int i=1; i<=n; i++) {
    dp[i] = min(dp[i-1], p[i]);
  }
  
  int maxx = -10001;
  for(int i=1; i<=n; i++) {
		int tmp = p[i] - dp[i-1];
    if(tmp>maxx) {
      max = tmp;
    }
  }
  cout<<max;
}

void f2() {
  dp[1] = a[1];
  for(int i=2; i<=n; i++)
    dp[i] = max(dp[i-1]+a[i], a[i]);
  
  int maxx = dp[1];
  for(int i=2; i<=n; i++)
    if(dp[i]>maxx) {
      maxx = dp[i];
    }
  cout<<maxx;
}

int main() {
  cin>>n;
  for(int i=1; i<=n; i++)
    cin>>a[i];

f1();
  //f2();
  return 0;
}
```

---

## 例题
- [4438   零钱兑换](http://39.99.183.126:8888/p/4438)

- [4439   打家劫舍](http://39.99.183.126:8888/p/4439)

- [4440   删除并获得点数](http://39.99.183.126:8888/p/4440)

---

|例题|
|----|
| [CCFPB01E03爬楼梯](http://39.99.183.126:8888/p/CCFPB01E03)          |
| [YBTJ1281最长上升子序列](http://39.99.183.126:8888/p/YBTJ1281)      |
| [P2403信封错排](http://39.99.183.126:8888/p/2403)  |
| [P204【基础】最大部分和（连续部分和）](http://39.99.183.126:8888/p/204)|