动态规划基础 - 动态规划

author: Ir1d, CBW2007, ChungZH, xhn16729, Xeonacid, tptpp, hsfzLZH1, ouuan, TrisolarisHD, HeRaNO, greyqz, Chrogeek, partychicken

动态规划应用于子问题重叠的情况：

1. 要去刻画最优解的结构特征；
2. 尝试递归地定义最优解的值（就是我们常说的考虑从 $i - 1$ 转移到 $i$ ）；
3. 计算最优解；
4. 利用计算出的信息构造一个最优解。

## 钢条切割

给定一段钢条，和不同长度的价格，问如何切割使得总价格最大。

为了求解规模为 $n$ 的原问题，我们先求解形式完全一样，但规模更小的子问题。
即当完成首次切割后，我们将两段钢条看成两个独立的钢条切割问题实例。
我们通过组合相关子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大者，构成原问题的最优解。

> 最优子结构：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

动态规划的两种实现方法：

- 带备忘的自顶向下法（记忆化搜索）；
- 自底向上法（将子问题按规模排序，类似于递推）。

算导用子问题图上按照逆拓扑序求解问题，引出记忆化搜索。

重构解（输出方案）：转移的时候记录最优子结构的位置。

## 矩阵链乘法

给出 $n$ 个矩阵的序列，希望计算他们的乘积，问最少需要多少次乘法运算？

（认为 $p \times q$ 的矩阵与 $q\times r$ 的矩阵相乘代价是 $p\times q\times r$ 。）

完全括号化方案是指要给出谁先和谁乘。

## 动态规划原理

两个要素：

### 最优子结构

具有最优子结构也可能是适合用贪心的方法求解。

注意要确保我们考察了最优解中用到的所有子问题。

1. 证明问题最优解的第一个组成部分是做出一个选择；
2. 对于一个给定问题，在其可能的第一步选择中，你界定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
3. 给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
4. 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。

要保持子问题空间尽量简单，只在必要时扩展。

最优子结构的不同体现在两个方面：

1. 原问题的最优解中涉及多少个子问题；
2. 确定最优解使用哪些子问题时，需要考察多少种选择。

子问题图中每个定点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。

**经典问题：**

-	**无权最短路径：** 具有最优子结构性质。
-	**无权最长（简单）路径：** 此问题不具有，是 NPC 的。区别在于，要保证子问题无关，即同一个原问题的一个子问题的解不影响另一个子问题的解。相关：求解一个子问题时用到了某些资源，导致这些资源在求解其他子问题时不可用。

### 子问题重叠

子问题空间要足够小，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。

### 重构最优解

存表记录最优分割的位置，就不用重新按照代价来重构。

## 最长公共子序列

子序列允许不连续。

每个 $c[i][j]$ 只依赖于 $c[i - 1][j]$ 、 $c[i][j - 1]$ 和 $c[i - 1][j - 1]$ 。

记录最优方案的时候可以不需要额外建表（优化空间），因为重新选择一遍（转移过程）也是 $O(1)$ 的。

## 最优二叉搜索树

给二叉搜索树的每个节点定义一个权值，问如何安排使得权值和深度的乘积最小。

考虑当一棵子树成为了一个节点的子树时，答案（期望搜索代价）有何变化？

由于每个节点的深度都增加了 1，这棵子树的期望搜索代价的增加值应为所有概率之和。

> tD/eD 动态规划：
> 状态空间是 $O(n^t)$ 的，每一项依赖其他 $O(n^e)$ 项。

## 最长连续不下降子序列

我们的目标是求出给定序列的一个最长的连续子序列，满足这个序列中的后一个元素 **不小于** 前一个元素。

因为是连续的，所以只要与上一个元素进行比较即可。

```cpp
int a[MAXN];
int dp() {
	int now = 1, ans = 1;
	for (int i = 2; i <= n; i++) {
		if (a[i] >= a[i - 1])
			now++;
		else
			now = 1;
		ans = max(now, ans);
	}
	return ans;
}
```

## 最长不下降子序列

与最长连续不下降子序列不同的是，不需要这个子序列是连续的了。

求最长子序列的方法有两种。

### 最简单的第一种

$O\left(n^2\right)$ 的算法。每一次从头扫描找出最佳答案。

```cpp
int a[MAXN], d[MAXN];
int dp() {
	d[1] = 1;
	int ans = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++)
			if (a[j] <= a[i]) {
				d[i] = max(d[i], d[j] + 1);
				ans = max(ans, d[i]);
			}
	}
	return ans;
}
```

### 稍复杂的第二种

$O\left(n \log n\right)$ 的算法，参考了这篇文章 <https://www.cnblogs.com/itlqs/p/5743114.html> 。

首先，定义 $a_1 \dots a_n$ 为原始序列， $d$ 为当前的不下降子序列， $len$ 为子序列的长度，那么 $d_{len}$ 就是长度为 $len$ 的不下降子序列末尾元素。

初始化： $d_1=a_1,len=1$ 。

现在我们已知最长的不下降子序列长度为 1，那么我们让 $i$ 从 2 到 $n$ 循环，依次求出前 $i$ 个元素的最长不下降子序列的长度，循环的时候我们只需要维护好 $d$ 这个数组还有 $len$ 就可以了。 **关键在于如何维护。**

考虑进来一个元素 $a_i$ ：

1. 元素大于 $d_{len}$ ，直接 $d_{++len}=a_i$ 即可，这个比较好理解。
2. 元素等于 $d_{len}$ ，因为前面的元素都小于它，所以这个元素可以直接抛弃。
3. 元素小于 $d_{len}$ ，找到 **第一个** 大于它的元素，插入进去，其他小于它的元素不要。

那么代码如下：

```cpp
for (int i = 0; i < n; ++i) scanf("%d", a + i);
memset(dp, 0x1f, sizeof dp);
mx = dp[0];
for (int i = 0; i < n; ++i) {
	*std::upper_bound(dp, dp + n, a[i]) = a[i];
}
ans = 0;
while (dp[ans] != mx) ++ans;
```

## 经典问题（来自习题）

### DAG 中的最长简单路径

$dp[i] = \max(dp[j] + 1), ((j, i) \in E)$

### 最长回文子序列

$$
dp[i][i + len] =
\begin{cases}
dp[i + 1][i + len - 1] + 2,	& \text{if}\ s[i] = s[i + len] \\\\[2ex]
\max(dp[i + 1][i + len], dp[i][i + len - 1]), & \text{else}
\end{cases}
$$

边界： $dp[i][i] = 1$ 。

注意： $dp[i][j]$ 表示的是闭区间。

也可以转化为 LCS 问题，只需要把 $a$ 串反转当做 $b$ ，对 $a$ 和 $b$ 求 LCS 即可。

证明在 [这里](https://www.zhihu.com/question/34580085/answer/59539708) 。

注意区分子串（要求连续）的问题。

### 最长回文子串

$O(n^2)$ ： $dp[i] = \max(dp[j] + 1), s(j + 1 \cdots i)$ 是回文

$O(n)$ ：Manacher

$p[i]$ 表示从 $i$ 向两侧延伸（当然要保证两侧对应位置相等）的最大长度。

为了处理方便，我们把原串每两个字符之间加一个（不包含在原串中的） `#` ，开头加一个 `$` 。

这样得到的回文串长度就保证是奇数了

考虑如果按顺序得到了 $p[1 \cdots i - 1]$ ，如何计算 $p[i]$ 的值？

如果之前有一个位置比如说是 $id$ ，有 $p[id] + id > i$ 那么 $i$ 这个位置是被覆盖了的，根据 $id$ 处的对称性，我们找 $p[id \times 2 - i]$ 延伸的部分被 $p[id]$ 延伸的部分所覆盖的那段，显然这段对称回去之后是可以从 $i$ 处延伸出去的长度。

如果找不到呢？就先让 $p[i] = 1$ 吧。

之后再暴力延伸一下。

可以证明是 $O(n)$ 的。

至于如何找是否有这么一个 $id$ 呢？递推的时候存一个 $max$ 就好了。

代码在： <https://github.com/Ir1d/Fantasy/blob/master/HDU/3068.cpp>

### 双调欧几里得旅行商问题

好像出成了某一年程设期末。

upd：其实是 [程设期末推荐练习](https://ir1d.cf/2018/06/23/cssx/程设期末推荐练习/) 里面的。

书上的提示是：从左到右扫描，对巡游路线的两个部分分别维护可能的最优解。

说的就是把回路给拆开吧。

#### 思路一

$dp[i][j]$ 表示 $1 \cdots i$ 和 $1 \cdots j$ 两条路径。

我们可以人为要求 $1 \cdots i$ 是更快的那一条路径。

这样考虑第 $i$ 个点分给谁。

如果是分给快的那条：

$dp[i][j] = \min(dp[i - 1][j] + dis[i - 1][i]),\ j = 1 \cdots i$

如果是慢的，原来是慢的那条就变成了快的，所以另一条是到 $i - 1$ 那个点：

$dp[i][j] = \min(dp[i - 1][j] + dis[j][i]),\ j = 1 \cdots i$

答案是 $\min(dp[n][i] + dis[n][i])$ 。
（从一开始编号，终点是 $n$ ）

代码： <https://github.com/Ir1d/Fantasy/blob/master/openjudge/cssx/2018rec/11.cpp>

#### 思路二

把 $dp[i][j]$ 定义反过来，不是 $1 \cdots i$ 和 $1 \cdots j$ 。

改成是 $i..n$ 和 $j \cdots n$ ，不要求哪个更快。

这样的转移更好写：

我们记 $k = \max(i, j) + 1$

$k$ 这个点肯定在两条路中的一个上， $dp[i][j]$ 取两种情况的最小值即可。

$dp[i][j] = \min(dp[i][k] + dis[k][j], dp[k][j] + dis[i][k])$

边界是： $dp[i][n] = dp[n][i] = dis[n][i]$ 。

答案是 $dp[1][1]$ 。

### 整齐打印

希望最小化所有行的额外空格数的立方之和。

注意到实际问题要求单词不能打乱顺序，所以就好做了起来。 **不要把题目看复杂。**

$dp[i] = \min(dp[j] + cost[j][i])$

不知道这样可不可做：有 $n$ 个单词，可以不按顺序打印，问怎么安排，使得把他们打印成 $m$ 行之后，每行的空格之和最小。

### 编辑距离

变换操作有 $6$ 种，复制、替换、删除、插入、旋转、终止（结束转换过程）。

### 最优对齐问题

把空格符插入到字符串里，使得相似度最大。

定义了按字符比较的相似度。

然后发现最优对齐问题可以转换为编辑距离问题。

相当于仅有三个操作的带权编辑距离。

```text
copy		:	1
replace : -1
insert	: -2
```

### 公司聚会计划

没有上司的舞会。

$dp[x][0]$ 是没去， $dp[x][1]$ 是去了。

$dp[u][0] = \max(dp[v][0], dp[v][1]), v \in son(u)$

$dp[u][1] = w[u] + dp[v][0], v \in son(u)$

### 译码算法

[Viterbi algorithm](https://en.wikipedia.org/wiki/Viterbi_algorithm) 之前写词性标注的时候有用到，好像用在输入法里面也是类似的。

本题中用来实现语音识别，其实就是找一条对应的概率最大的路径。

ref： <https://segmentfault.com/a/1190000008720143>

### 基于接缝裁剪的图像压缩

玩过 opencv 的应该有印象，seam carving 就是在做 dp。

题中要求每一行删除一个像，每个像素都有代价，要求总代价最小。

限制：要求相邻两行中删除的像素必须位于同一列或相邻列。

$dp[i][j] = \min(dp[i - 1][j], dp[i - 1][j - 1], dp[i - 1][j + 1]) + cost[i][j]$

边界： $dp[1][i] = cost[1][i]$ 。

### 字符串拆分

相当于问怎么按顺序拼起来使得总代价最小。

等价于之前那个最优二叉搜索树。

$dp[i][j] = \min(dp[i][k] + dp[k][j]) + l[j] - l[i] + 1,\ k = i + 1 \cdots j - 1$

注意 $l[i]$ 表示的是第 i 个切分点的位置。

边界： $dp[i][i] = 0$ 。

就按照区间 dp 的姿势来写就好了。

### 投资策略规划

> 引理：存在最优投资策略，每年都将所有钱投入到单一投资中。

这是个很有趣的结论，dp 问题中很常见。

<https://fogsail.github.io/2017/05/08/20170508/>

剩下的就是个二维 dp，想成从 $(1, i)$ 走到 $(n, m)$ 的路径的问题，然后收益和代价就是边权，网格图只能往右下方走。

### 库存规划

生产多了少了都有额外的成本，问怎么安排生产策略使得额外的成本尽可能地少。

$cost[i][j]$ 表示剩下 $i$ 个月，开始的时候有 $j$ 台库存的最小成本。

<https://walkccc.github.io/CLRS/Chap15/Problems/15-11/>

### 签约棒球自由球员

$v[i][j]$ 是考虑 $i$ 之后的位置，总费用为 $x$ 的最大收益。

<https://walkccc.github.io/CLRS/Chap15/Problems/15-12/>

类似于背包问题。

* * *

当选取的状态难以进行递推时（分解出的子问题和原问题形式不一样），考虑将问题状态分类细化，增加维度。

WIKIOI

动态规划基础 - 动态规划