[学习笔记]动态规划的一些基本概念和杂项

[学习笔记]动态规划的一些基本概念和杂项 动态规划是什么？

在学习一个算法之前，我们肯定要知道它是什么。

在笔者看来，与其说动态规划是一种算法，不如说它是一个思想。
怎样的思想呢？

1. 将大问题分解成本质相同但规模更小的子问题求解，再根据子问题的解求出原问题的解。这和分治算法的思想极为类似。
2. 不做重复的事情。如果一个问题已经被求解过了，我们就不要再求解它了。

说到这儿可能很抽象，我们来根据实际问题举一个例子：

Luogu P1255 数楼梯

（先不要考虑高精度算法。）

这是一个十分基础的动态规划问题。

首先，如果你不会动态规划，那么你的想法应该是暴力模拟，枚举每一步采取什么方案。很容易看出这是指数级的时间复杂度，时间爆炸。

分析为什么时间效率会很低，这是因为我们只要求最后的结果，但是我们求了每一步采取什么方案，这些信息是没用的。

考虑优化：为了求题目让我们求的方案数，我们可以设 f i f_i fi​ 表示从第 0 0 0 级台阶走到第 i i i 级台阶的方案数。如何求解 f i f_i fi​ 呢？

我们首先用到我们前面提到的第一个思想：我们发现，由于每一步都只能走一级台阶或二级台阶，所以我们要么从第 i − 1 i-1 i−1 级台阶走上来，要么从第 i − 2 i-2 i−2 级台阶走上来。易得：
f i = { 1 x ≤ 1 f i − 1 + f i − 2 x > 1 f_i = begin{cases} 1&x leq 1 \ f_{i - 1} + f_{i - 2}&x > 1 end{cases} fi​={1fi−1​+fi−2​​x≤1x>1​

这样的话，只要我们求出了 f i − 1 f_{i-1} fi−1​ 和 f i − 2 f_{i-2} fi−2​，我们就能求出 f i f_i fi​，第一个思想体现出来了。于是我们就能轻而易举地用递归的写法写出代码：

#include
using namespace std;
int n;
int f(int x)
{
    if (x <= 1)
        return 1;
    return f(x - 1) + f(x - 2);
}
int main() {
    cin >> n;
    cout << f(n);
    return 0;
}

经过试验后你会发现，最终我们还是会超时，分析一下原因：假如我们要求 f 6 f_6 f6​，就会求 f 5 f_5 f5​ 和 f 4 f_4 f4​，而求 f 5 f_5 f5​ 还要用到 f 4 f_4 f4​……以此类推，我们会发现很多 f f f 值被求了数次，效率很低。

这就用到了我们的第二个思想：我们可以开一个数组来记住已经求过的 f f f 值，下一次再要用的时候直接调用就好啦 OvO text{OvO} OvO

代码如下，加上高精度即可通过本题（为了更便于阅读我没有加高精度）：

#include
#include
using namespace std;
int n, dp[5005];
int f(int x)
{
    if(dp[x] != -1) //这个f值已经求过了
        return dp[x];
    if (x <= 1)
        return dp[x] = 1;
    return dp[x] = f(x - 1) + f(x - 2);
}
int main() {
    for(int i = 0; i <= 5000; i++)
        dp[i] = -1;
    cin >> n;
    cout << f(n);
    return 0;
}

由于每个状态最多被计算1次，所以时间复杂度为 O ( n ) O(n) O(n)。

通过这一题，我们就可以引出动态规划中的概念：

动态规划中的重要概念

动态规划中的基本概念有很多，比如阶段和阶段变量，状态和状态变量，决策、决策变量和决策允许集合，策略和最优策略，状态转移方程……但是，其中比较重要的就是状态和状态转移方程，在初学阶段我们也只需要掌握这两个基本概念。

什么是状态？

通俗地解释一下：状态就是我们面临着的某个局面，或者说是我们记录下的子问题的解/信息。

在前面的数楼梯问题中，我们用 f i f_i fi​ 表示从第 0 0 0 级台阶走到第 i i i 级台阶的方案数，这里的 f f f 就是状态。我们所记录的信息也是 f f f 的值。

这个概念可能很抽象，但是必须通过慢慢琢磨才能更好的理解这一概念。

什么是状态转移方程？

从一个状态的解，得知另一个状态的解，我们称之为“状态转移”。这个转移式子称为“状态转移方程”。

类似地，在上一个问题中，
f i = { 1 x ≤ 1 f i − 1 + f i − 2 x > 1 f_i = begin{cases} 1&x leq 1 \ f_{i - 1} + f_{i - 2}&x > 1 end{cases} fi​={1fi−1​+fi−2​​x≤1x>1​
就是我们的状态转移方程。

如何使用动态规划

两步走：

1. 设计状态，把所求问题用状态表示出来；
2. 设计转移，用小问题的解求大问题的解。

使用动态规划的情境

动态规划一般用来解决两种问题：最优解问题和方案计数问题。比如数楼梯问题就属于方案计数问题。

另外，面对具有重叠子问题性质，即我们要多次求解一个子问题的题目，很有可能要使用动态规划。

设计状态

设计状态时要“三思而后行”，必须满足以下原则：

1. 最优子结构性质：大问题的最优解一定是由小问题的最优解得来的，局部最优将导致全局最优；
2. 无后效性原则：“未来与过去无关”，现在的决策只来源于过去的结果，而与过去的决策无关。例如上楼梯问题中， f i f_i fi​ 依赖于 f i − 1 f_{i-1} fi−1​ 与 f i − 2 f_{i-2} fi−2​ 的值，我们不关心它们是怎么被求出来的。
3. 状态必须要能唯一、确定地表达一个局面！

后效性的消除

一种常见的做法是将决策写进状态中。

Codeforces GYM101502D Dice Game

设 f i f_i fi​ 表示得到 i i i 分的最少步数？不行，因为我们不知道骰子是从哪一面翻过来的，而我们不能翻转 180 ° 180degree 180°。所以这个状态是具有后效性的。

为了消除后效性，我们可以设 f i , j f_{i,j} fi,j​ 表示得到 i i i 分且翻过来时顶面分数为 j j j 的最少步数。那么我们就能轻松地写出状态转移方程。留作习题答案略，读者自得不难

设计转移

转移有两种形式：push型转移和pull型转移。

push 型转移：“我到哪里去”“我为人人”等词语都可以描述，当我们到达一个状态时，这个状态的值已经被求好，我们考虑它的所有去处，用这个状态的值去更新别的状态的值。比如数楼梯问题中，我们已经知道了 f i f_i fi​ 的值，我们就可以用它去更新 f i + 1 f_{i+1} fi+1​ 和 f i + 2 f_{i+2} fi+2​。主动地用自己的信息去更新别人的信息，所以得名 push。（我们要学习这种为他人无私奉献自我的精神！）

pull 型转移：与 push 相反，“我从哪里来”“人人为我”等词语都可以描述，当我们到达一个状态时，这个状态前面的所有状态的值都已经被求好，我们考虑它的所有来源，用别的状态的值去更新它的状态的值。比如数楼梯问题中，我们的状态转移方程就是 pull 型转移。别的状态的信息被动地被拉过来更新它的值，所以得名 pull。

大多数情况下，push 型和 pull 型没太大差别，但是还是有特殊情况的：

Codeforces 1350B Orac and Models

设 d p i dp_i dpi​ 表示在选择第 i i i 个模型的情况下的最长美丽子序列长度，则
d p i = max ⁡ j ∣ i , s j < s i { d p j + 1 } dp_i = max_{j|i,s_j

如果我们采用 pull 型转移，枚举 i i i 的因数，时间复杂度为 O ( n n ) O(n sqrt{n}) O(nn ​)；而如果我们采用 push 型转移，枚举 i i i 的倍数，时间复杂度变成 O ( n log ⁡ n ) O(n log n) O(nlogn)，且 push 的代码更为简短。可以看一下：

#include
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int a[maxn], dp[maxn];

void work()
{
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", a + i);
	for(int i = 1; i <= n; i++)
		dp[i] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = i + i; j <= n; j += i)
			if(a[j] > a[i])
				dp[j] = max(dp[j], dp[i] + 1);
	int ans = 0;
	for(int i = 1; i <= n; i++)
		ans = max(ans, dp[i]);
	cout << ans << endl;
}

int main()
{
	int T;
	cin >> T;
	while(T--)
		work();
	return 0;
}

动态规划的实现方式

有两种：

自顶向下的备忘录法（记忆化搜索）

我们回顾一下数楼梯问题的代码：

#include
#include
using namespace std;
int n, dp[5005];
int f(int x)
{
    if(dp[x] != -1) //这个f值已经求过了
        return dp[x];
    if (x <= 1)
        return dp[x] = 1;
    return dp[x] = f(x - 1) + f(x - 2);
}
int main() {
    for(int i = 0; i <= 5000; i++)
        dp[i] = -1;
    cin >> n;
    cout << f(n);
    return 0;
}

这就是记忆化搜索。

自底向上的动态规划（常规形式，按顺序递推）

我们继续以数楼梯问题为例：

#include 
using namespace std;
int a[5005], n;
int main()
{
    scanf("%d", &n);
    a[0] = a[1] = 1;
    for (int i = 2; i <= n; i++)
        a[i] = a[i - 1] + a[i - 2];
    printf("%d", a[n]);
    return 0;
}

两种方法各自的优点 记忆化搜索

• 可以在没思路的时候帮助你想思路；
• 写完暴力的搜索后很容易加上记忆化；
• 转移顺序不便考虑时可以省事，比如 NOIP提高组2010 乌龟棋 这道题，转移顺序不好安排，可以考虑记忆化；
• 有时可以节省时间和空间，因为达不到的状态是不会被搜到的，这一点在状压DP中体现得很明显。

推荐题目：Luogu P1464 Function

按顺序递推

• 代码更为简短；
• 大部分情况下可以提高时间效率，因为记忆化搜索的递归会产生额外的开销。

另外，推荐阅读《聊聊动态规划与记忆化搜索》。

动态规划的时间复杂度

设状态个数为 N N N，每个状态的转移复杂度为 C C C。那么在绝大多数情况下，时间复杂度为 O ( N × C ) O(N times C) O(N×C)。

动态规划的分类

动态规划较难的一个重要原因是它不像树状数组、线段树等数据结构，或拓扑排序算法一样有具体的模板，但是动态规划是可以分类的。索引的目录就是这样诞生的。

决策方案的输出

比较常见的方法是转移时记录下每一步的决策（从哪个状态转移过来的），输出方案时逆推。