状态设计

动态规划是 OI 最重要的部分之一。从学习与做题的角度来说，主要分为设计状态与优化两部分。其中前者更多的是做题和总结方法与套路，甚至需要一定的灵感；而后者相对吃经验。

值得注意的是，很多题目都要求我们在设计算法以前先将题目进行一定的转化，从而将一个不熟悉的模型转化为我们更容易把握的模型。这一点在动态规划的题目中体现的尤为明显。

在阅读本文之前，你应该对动态规划有基本的了解。

线性 DP

在线性结构上枚举每一维度进行转移的 DP。

直接做怎么做？设 $f_{i,j,k}$ 表示前 $i$ 个数，当前前缀和为 $j$，最大前缀和为 $k$，然后枚举填什么刷表转移对于每个状态是 $O(1)$ 的，虽然能做，但是状态数炸了。

需要合并无效状态。同时记录前缀和和最大前缀和有些冗余，从这里入手。考虑对于一段后缀，如果它本身的最大前缀和是 $0$，那么它不会对前面的贡献产生影响，这时可以直接确定排除掉这段后缀的前缀的答案，也就是题目所求。

设 $f_{i,j}$ 代表考虑前 $i$ 个数，且满足 $[i+1,n]$ 的最大前缀和为 $j$ 的期望答案，答案是 $f_{i,0}$。那么转移：

• 如果 $j>0$，可以以 $p_i$ 的系数（第 $i+1$ 位填 $1$）转移到 $f_{i+1,j-1}$，$1-p_i$ 的系数（第 $i+1$ 位填 $-1$）转移到 $f_{i+1,j+1}$。
• 如果 $j=0$，那么第 $i+1$ 位一定是 $-1$，此时可以转移到 $f_{i+1,0}$ 和 $f_{i+1,1}$。

代码。

背包

基本模型：01 背包、完全背包、多重背包、分组背包、方案数背包的撤回（将转移的东西减去即可）。

为方便分析时间复杂度，记 $M=\max\{C,D\}$。

考虑 $K=0$ 怎么做。分别考虑划分两种特征，两次背包分别对工具箱和螺丝进行 DP 即可。

发现 $K$ 很小，考虑针对它设计状态。对于不是这 $K$ 个没事找事的螺丝，前面的 DP 做法依然成立。然后再考虑这些没事找事的。

设 $F(i,j,k)$ 代表考虑前 $i$ 个工具箱，普通螺钉的重量为 $j$，三角螺纹的重量为 $k$。需要枚举当前的选的东西是什么和上一个东西是什么。滚掉 $i$ 这一维，所有状态都是可以转移的，考虑用这种方式处理没事找事的螺丝，时间复杂度为 $O(k^2 w M)$。

然后枚举体积，进行背包合并即可。代码。

区间 DP

图上 DP

一般的图上 DP 建立在 DAG 结构上。

树上背包

* [福建省队集训 2019] 最大权独立集问题

Portal.

好题！如果你之前没怎么学明白，这道题能让你对树形背包的理解加深不少。

删点相当于什么？当前这个点的信息会走到与它连接的未被删去的点，也就是给边定向。那么不难发现问题相当于给边定向，然后每个点的权值是 $a_i\times |i 能到达的点的个数|$。

因此设 $f_{x,i}$ 代表连 $fa_x \to x$，$x$ 可到达子树内（含本身）的 $i$ 个点（它不会到达子树外面的点）；$g_{x,i}$ 代表连 $x\to fa_x$，$x$ 可到达子树外的 $i$ 个点（在转移时，它的父亲不会关心它能到达子树中的几个点）。

现在考虑计算 $x$ 点的答案。比如说要算 $g$，能根据其孩子的 $g$ 信息来确定吗？不太方便，因为孩子的 $g$ 和当前 $x$ 选择了多少个孩子的 $f$ 是有关的。不一定不能做，总之不太方便。

本身 $x$ 点还是要计算贡献的，因此我们不妨直接钦定其能走到树上的 $j$ 个节点，然后关系到这个信息填进哪个 $f,g$ 值，因此设 $h_{i,j}$ 代表走到 $i$ 个子树内的点，总共能走到 $j$ 个点的代价。算出 $h$ 数组后不难求出 $f_x,g_x$。转移就不难了。

qoj14416 只是把 $\min$ 改成 $\max$，代码。

父亲向子树转移

[Nanjing Regional 2024] Topology

Portal.

设状态为考虑子树内的信息是很奇怪的事情，因为你不知道外部的拓扑序是怎么排的。

因此设 $f_{x,i}$ 代表删除 $x$ 子树内的所有节点（不含 $x$）之后，使得 $x$ 的拓扑序为 $i$ 的拓扑序个数。转移的时候从父亲转移到儿子，每次考虑除了 $y$ 以外 $x$ 的所有儿子。代码。

换根 DP

如果我们需要对所有点都当作根进行一次树形 DP，那么我们可以使用换根 DP 来处理。

[AMPPZ 2023] Routing K-Codes

Portal.

不难观察出只有二叉树是有答案的。其实就是根节点一定填 $1$（填 $0$ 则删掉这个点），然后左右儿子一个填 $2i$ 另一个填 $2i+1$，树形 DP 可以完成。

由于转移途中不止有加减法而且 DP 数组不止一个，换根可能很麻烦。推荐一种非常美观的换根写法：在第二次 DFS 时记录一个 Node 类型代表父亲的答案。重载 Node 类型的加法即可很方便的完成换根。

代码。

例题

[Jinan Regional 2024] DFS Order 2

Portal.

还是只能考虑父亲向子树转移，$f_{x,i}$ 表示 $x$ 节点在 DFS 序中的 $i$ 号位置，然后转移到孩子。考虑在转到儿子之前，应该先遍历了一些其它儿子，然后再遍历完目标儿子之后再回来遍历其它孩子，是一个树形背包的形式，然后要乘上一些阶乘。

写起来挺爽。

代码。

状压 DP 与轮廓线 DP

动态 DP

其它 DP

一些杂项内容

插入法

数位 DP

一般的数位 DP 直接采用记忆化搜索实现即可。

手机号码，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

int num[15];
int f[11][11][11][2][2][2];

i64 dp(int p, int p1, int p2, bool unlim, bool d, bool _4, bool _8) {
    if (_4 && _8) return 0;
    if (p == 0) return d;
    if (unlim && f[p][p1][p2][d][_4][_8] != -1) return f[p][p1][p2][d][_4][_8];
    i64 res = 0; int mx = unlim ? 9 : num[p];
    for (int i = 0; i <= mx; ++i)
        res += dp(p - 1, i, p1, unlim || (i < mx), d || (i == p1 && i == p2), _4 || (i == 4), _8 || (i == 8));
    if (unlim) f[p][p1][p2][d][_4][_8] = res;
    return res;
}

i64 calc(i64 n) {
    memset(f, 0xff, sizeof f);
    for (int i = 1; i <= 11; ++i, n /= 10) num[i] = n % 10;
    i64 res = 0;
    for (int i = 1; i <= num[11]; ++i) 
        res += dp(10, i, -1, i < num[11], 0, i == 4, i == 8);
    return res;
}

int main(void) {
    i64 l, r; cin >> l >> r; cout << calc(r) - calc(l - 1) << "\n";
    return 0;
}

例题

刷基础 1

只有 NOIP 难度。

[CSP-S 2024] 染色

Portal.

设 $f_i$ 代表考虑前 $i$ 位的答案。只有 $lst_{a_i}$ 可以与 $a_i$ 匹配，如果要匹配，中间一大段都要染成同一个颜色，计算这一段有多少贡献，从 $f_{lst_{a_i} + 1}$ 转移过来。

记录前缀某一段的贡献即可快速计算任意一段有多少贡献。代码。

[2023 钉耙编程 1] Mr. Liang play Card Game

Portal。很有合并的感觉！考虑区间 DP，最后你会将区间合到只剩一张牌，于是设一个四维状态就可以直接转移。代码。

刷提升 1

比较有趣。

[Ptz 2020 Summer Day4] Ternary String Counting

Portal.

$O(n^4)$ 直接 $f_{i,x,y,z}$ 记录每一个字符出现的位置，$O(n^3)$ 记录前两个不同字符的出现位置。都需要前缀和优化。

状态数还是过多了，我们需要寻找一个方式简化。先把转移写出来（对于状态 $f(i,j,k)$，表示当前考虑到第 $i$ 位，与这一位不同的数字上一次出现的位置分别位 $j,k$，并且 $j>k$）：

• $f(i+1,i,k)\stackrel{+}\leftarrow f(i,j,k)$；

• $f(i+1,i,j)\stackrel{+}\leftarrow f(i,j,k)$；

• $f(i+1,j,k)\stackrel{+}\leftarrow f(i,j,k)$。

再考虑题目中的限制，实际上就是限制了 dp 过程中 $j$ 和 $k$ 的取值范围：

1. $x=1$，则 $j<l$；
2. $x=2$，则 $j\ge l,k<l$；
3. $x=3$，则 $k\ge l$。

考虑优化，看上去第一维什么都不是！将转移分为 $i$​ 层，每一层的状态只能从上一层转移过来，第三个转移就是直接从上一层的对应点转移，第一二个转移是对上一层的一列和一行求和。

等价于，每次给出一个矩形，先把矩形外的值全部清零。然后还可以发现，一旦某个值被清零，那么这个值以后永远都是零。并且对于某一行来说，非零的值永远是一段连续区间，而且其位置是单调的。

双指针扫，不重复清零某个行即可。最终时间复杂度 $O(n^2+m)$。代码。