动态规划初步

动态规划（DP）教程

大家好，我是Weekoder！

Week_team 的同学们都来听课啦！

如果你还没有加入 Week_team，点击这里即可加入我们！

动态规划的概念

动态规划（DP）听起来是个非常吓人的东西，实际上……确实是个吓人的东西。但是我想告诉大家，动态规划并没有那么难，主要有两个关键点：

• 多练。

• 多思考。

就是这么简单。

但实际做起来却不简单。

那么，我们伟大旅程的第一步就是——搞懂动态规划是什么！

首先，动态规划也称 DP，他适合解决的问题类型有两种：

• 最值问题。（最大最小值）

• 计数问题。（请问一共有多少种方案数？）

只要知道这些就够了。

那 DP 又分为哪几个步骤呢？

1. 找到决策。

2. 设计状态。

3. 考虑转移。

没有看懂没关系，我们一个个来。

以B3636为例子，展开我们的讲解。

1. 找到决策

这一步比较简单，但也是最重要的一步。

题目描述里有这样一段话：

机器猫有两种操作可以做。假设现在已经有 \(x\) 个字，机器猫可以选择：

• 往文档最后加一个字。字数变成 \(x+1\)。
• 把文档复制粘贴一遍。字数变成 \(2x\)。

这给了我们一个启发。假设现在你是机器猫，你坐在电脑前开始打字。哒哒哒哒哒哒哒哒哒哒哒（超真实打字音效）。你的屏幕上有若干个字，这时候就到了最让人犯难的时候了：到底该加一个字还是粘贴一遍？答案是不需要知道。唯一需要知道的是当前有两个选择：加字和粘贴一遍。这就是我们的决策。

恭喜你找到决策了！啪啪啪啪啪（鼓掌）！

简单总结：找到决策就是模拟一遍题目的过程，找到需要进行抉择的地方。

2. 设计状态

设计状态对初学者来说往往是很让他们困扰的。那该怎么办呢？最好的方法还是多练。但这里我也会提供一种设计状态的思路。

状态是什么？我们在求解动态规划问题时，往往需要数组，如 \(dp[10010]\)。你可以把状态理解为你对数组元素的定义。如对于这道题，我们可以把 \(dp_i\) 定义为打了 \(i\) 个字所需要的最少步骤，那么答案就是 \(dp_n\)（打 \(n\) 个字所需要的最少步骤）。这就像你对函数意义的定义。

那我们拿到一道题之后该怎么去定义呢？其实对于我，一开始的时候可以定义的比较随便。但一旦发现很难求解，就要及时考虑加入状态。比如定义的状态是 \(dp_i\)，那么就加入一个 \(j\)，变为 \(dp_{i,j}\)。在各种各样的题目中，甚至会出现四维数组 \(dp_{i,j,k,l}\)。

那么这道题的状态就设计为 \(dp_i\) 表示打 \(i\) 个字所需要的最少步骤。

注意：最好的方法还是多练，多刷题！

3. 考虑转移

这是很多人眼中最难的一步。其实我觉得这一步并没有设计状态难，因为他和第一步是紧密相关的。

我们第一步说到了决策，那我们就要想一想怎么利用这个决策把状态一一填满。

这个时候其实是要设计一个状态转移方程。就像这样：

现在我们要把这个 \(?\) 填上。我们想一想 \(dp_i\) 能从哪个地方做决策而来？就像已经打了 \(i\) 个字的机器猫，想知道他有可能是打了几个字的机器猫做了一步决策而来的。显然，我们之前说过，机器猫要么只能打一个字（\(x+1\)），要么只能粘贴一遍文本（\(2x\)）。现在反过来看，不就是打了 \(i-1\) 和 \(i\div2\) 个字的机器猫吗？一个打一个字就变成了 \(i\)，另一个粘贴一遍文本也变成了 \(i\)。那我们既然要求最小步骤，肯定要在两种情况里取最小值再加上做出决策的步骤（\(1\) 步）啦。看看状态转移方程吧：

这样就设计成功了！

其实我认为，状态转移方程就是决策的逆运算。

这样就结束了。

还有一点比较重要的是，设定初始状态。像刚才的例子，初始状态就是 \(dp_1=0\)，因为一开始就有一个字，不需要进行任何操作。当然，全局数组默认是 \(0\)，所以不需要单独加上这样一条指令。

我们只需要循环从小到大扩展，套用状态转移方程就行了。

\(\text{Code:}\)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, dp[N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 2; i <= n; i++) {
        if (i % 2 == 0)
            dp[i] = min(dp[i - 1], dp[i / 2]) + 1;
        else
            dp[i] = dp[i - 1] + 1;
    }
    cout << dp[n];
    return 0;
}

这里有一个细节，就是在循环里并没有直接套用公式，而是判断了字数的奇偶。因为当字数为奇数时，是不可能从 \(i\div2\) 转移过来的。而奇数的情况一定不能写成这样：

这里不能取 min，因为只有 \(i-1\) 这一种情况，上面的是在两种情况：\(i-1\) 和 \(i\div2\) 中取 min。在求最值问题时才会有上面这种写法。

总结

我相信如果你是初学者，光看代码看定是不能完全看懂的。可以私信我 @Weekoder 或者在评论区发表意见和疑问。

作业：动态规划初步题单。

再见！