本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-11 20:40:50

浅谈 dp 的分步转移

顾名思义，分步转移是一种类似人走路一样的一步一步转移的方式。

分步转移常常用于有多个维度的 dp 转移，它可以将多个维度一起转移转化为一个维度一个维度的转移，从而降低转移的复杂度。

dp 的几个维度之间可能有关联，但是不能影响到权值的计算，我们称之为“弱关联”。

例如，对于二维的状态 $(a,b)\to (a',b')$，dp 的转移中有形如 $w(a',b')$ 的权值，那么分步之后不会影响我们的权值计算，依然可以采用分步转移进行优化。

如果 dp 的权值依赖于上一个状态，有多维状态之间的联系，那么就不能用分步转移的方式。

举个例子，对于二维的状态 $(a,b)\to (a',b')$，如果转移中包含形如 $w(a',b)$ 或者 $w(a,b')$ 的值，就不适用于分步转移，因为分步之后无法计算新的权值。

干讲可能有些抽象，有几个例子可以让大家辅助理解。

Problem - 633F - Codeforces

简要题意：在树上选两条路径，使他们的点权和最大。

直接做显然是困难的。

一条路径 $u\to v$ 显然可以分成 $u\to \operatorname{lca}$ 和 $v\to \operatorname{lca}$ 两部分。

我们考虑如果是选一条路径，那么我们就是直接选直径，我们在选直径的时候是如何考虑的呢？

就是直接在子树内选最长和次长链，然后尝试拼起来。

所以我们可以考虑模仿这个过程，设 $f_{u,0/1/2/3}$ 分别表示在 $u$ 节点的子树内，目前分别选了一条不完整的链（即可以向上继续延伸）、一条完整的链（不能向上）、一条完整的和一条不完整的链、两条完整的链的最大权值。

转移的话就是考虑将不同的情况拼在一起，需要自己推一推，有一些细节，但是总体难度不高。

这道题就是把选路径的过程拆分成了多种情况，然后一步一步的补全两条链，从而实现转移，体现了拆分分步的思想。

P12738 [POI 2016 R2] 口吃 Stutter - 洛谷

简要题意：你有两个序列 $\{a_i\}$ 和 $\{b_i\}$，你要选出两个序列的最长的满足以下要求的子序列：

• 子序列的长度为偶数。
• 设 $\{t_i\}$ 子序列的长度为 $2k$， $\forall 1\le i\le k,t_{2i-1}=t_{2i}$。

空间限制 32 MB。

首先，对于一个 $a_i$，它如果要计入子序列中，一定是与前面或者后面的离他最近的进行匹配，放到子序列相邻的位置上，否则一定不优，对于 $b_i$ 同理。

显然，我们有暴力 dp 的做法。

我们可以直接设 $f_{i,j}$ 表示 $\{a_i\}$ 用前 $i$ 个数，$\{b_i\}$ 用前 $j$ 个数的最长长度。

转移是容易的，直接效仿求 LCS 的 dp 转移即可，设 $nxta_i$ 表示序列 $a$ 中 $i$ 后面第一个与它相等的数的位置，$nxtb_i$ 的定义类似。

转移就是 $f_{i,j}\to f_{i+1,j}$，$f_{i,j}\to f_{i,j+1}$，$(f_{i,j}+2)\times [a_{i+1}=b_{j+1}]\to f_{nxta_{i+1},nxtb_{j+1}}$。

但是此时空间复杂度为 $O(n^2)$，难以接受。

一个显然的想法是将枚举的时候将第一位压掉，但是很有问题啊，我们丢失了一维信息之后，我们转移没法转了。

由于我们扩展出来的子序列与原来选的没有关系，只与 $a_{i+1}$ 与 $b_{j+1}$ 是否相等有关系，所以我们考虑分步转移。

设 $f_{i,j,0/1/2/3}$ 分别表示 $\{a_i\}$ 用前 $i$ 个数，$\{b_i\}$ 用前 $j$ 个数，现在应该转移下一对数中 $a$ 中的第一个数、$b$ 中的第一个数、 $a$ 中的第二个数、$b$ 中的第二个数的最长长度，然后要求 $1、2、3$ 状态满足 $a_i/b_j$ 必须是最后一个选的数（为了满足转移的要求）。

$f_{i,j,0} \to f_{i+1,j,0}$，$f_{i,j,0}\to f_{i,j+1,0}$，$f_{i,j,0}+1 \to f_{k,j,1}$，$f_{i,j,1} \times[a_i=b_k] \to f_{i,k,2}$，$f_{i,j,2}\times[a_k=b_j] \to f_{k,j,3}$，$f_{i,j,3}\times[a_i=b_k] \to f_{i,k,0}$。

显然转移和上面差不多，每次枚举到在另一个序列上相等的就转移，答案就是所有 $0$ 状态的最大值。

现在我们再对新的状态压掉第一维，我们发现不会出问题了，因为我们省去了对于 $nxt$ 的转移。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$，常数有点大。

所以由此可见，通过分步转移的方式，我们拆分的原有的 dp 状态，可以优化一部分题目的时间。

P7648 [COCI 2012/2013 #5] MNOGOMET - 洛谷

题意过于复杂，不在赘述。

我们发现，如果直接 dp 记录时间，人，比分，队伍等信息，会让复杂度变的非常高，不可接受。

我们现在考虑发掘一点点性质。

由于每次射门后，球都回到自己队伍的 $1$ 号队员手中，所以我们可以把每一次射门看作一步，每次射门之间都是独立的情况。

我们将球的可传导关系刻画到图 $G$ 上。

设 $g_{0/1,t,i}$ 表示说，求球最开始在某个队伍的 $1$ 号队员手中，经过 $t$ 时间后，到 $i$ 号球员手中的概率。

$g_{0/1,t,u} \times [(u,v)\in G]\to g_{0/1,t+1,v}$。（箭头只表示转移关系）

然后设 $w_{0/1,0/1,t}$ 表示球开始在某个队手上，$t$ 秒后在某个队手上，射门后球进了的概率，$l_{0/1,0/1,t}$ 表示球开始在某个队手上，$t$ 秒后在某个队手上，射门后球没进的概率。

这个是好算的，直接枚举每个人，用 $g$ 算出来即可。

设 $f_{t,i,j,0/1}$ 表示经过 $t$ 秒，比分为 $i:j$ ，球现在在某个队的 $1$ 号选手的手上的概率。

这个直接枚举经过的时间，也是好转移的。

$f_{t,i,j,0}\times w_{0,0,t'-t} \to f_{t',i+1,j,0}$，$f_{t,i,j,0}\times w_{0,1,t'-t} \to f_{t',i,j+1,1}$。

$f_{t,i,j,1}\times w_{1,0,t'-t} \to f_{t',i+1,j,0}$，$f_{t,i,j,1}\times w_{1,1,t'-t} \to f_{t',i,j+1,1}$。

$f_{t,i,j,0}\times l_{0,0,t'-t} \to f_{t',i,j,0}$，$f_{t,i,j,0}\times l_{0,1,t'-t} \to f_{t',i,j,1}$。

$f_{t,i,j,1}\times l_{1,0,t'-t} \to f_{t',i,j,0}$，$f_{t,i,j,1}\times l_{1,1,t'-t} \to f_{t',i,j,1}$。

但是还有问题，我们的问题是求出每一粒进球后比赛结束的概率。

如果某个状态之后还有射门，那我们不用管。

现在的问题是，如果某一次射门之后没有射门了？

我们再设 $q_{0/1,t}$ 表示开始球在某个队手中，经过 $t$ 秒都没有射门的概率。

$q_{0/1,t}=\sum_u g_{0/1,t,u}$。

时间复杂度 $O(T^2n^2)$。

所以我们用分步转移的方式降低了时间复杂度。

参考了题解：https://www.luogu.com.cn/article/82old07u 的思路。

总结

分步转移是一种 dp 状态的设计方式，通过拆分或合并转移中本质相同的过程或状态，可以降低复杂度，达到我们的目的。

其核心思想是，要发掘 dp 状态和转移本身的性质，找出正确的分步方式，合并一些本质相同的状态或过程，抑或是将一个过程拆分成多步来达到简化转移的目的，设计出正确的状态。

作为一种小 trick，可以降低一些思考的难度，也有一些例题和应用。

参考

部分参考了文章：https://www.cnblogs.com/A-Quark/p/16448270.html 和 https://www.cnblogs.com/cqbzlym/p/18996536 的例题及表述，在此表示感谢。

参考了题解：https://www.luogu.com.cn/article/82old07u 的思路，在此表示感谢。