DP 套 DP
引入
本文将介绍 DP 套 DP 的思想，并通过两道例题展示它如何应用到具体问题中．
思想
所谓「DP 套 DP」，实际上指的是在动态规划的过程中，把一个子问题的求解过程（通常是一个 DP）抽象成一个自动机（DFA），然后在这个自动机的基础上再设计一层新的 DP 的方法．
这种技巧主要应用于一类 序列计数 、概率 或 期望 问题．一个典型的问题具有如下结构：
- 给定字符集 ΣΣ
和它上面一个长度为 𝑛n 的「合法序列」的集合 𝐴 ⊆Σ𝑛A⊆Σn．根据字符集不同，序列可以是二进制串、数字串、状态序列等． - 对于每一个具体的序列 𝑠 ∈Σ𝑛s∈Σn，可以通过动态规划来判断它是否合法（即 𝑠 ∈𝐴s∈A），计算它的权值或求出相关值．
- 最终，我们希望统计集合 𝐴A 中所有序列的数目、总权值、期望值等．
这时，枚举所有序列是不可行的．于是我们考虑将「判断一个序列是否合法」的过程（即内层 DP）抽象为一个 确定有限状态自动机（DFA）．一般地，对于固定的序列 𝑠 ∈Σ𝑛s∈Σn，内层 DP 的状态函数可以表示为 𝑔(𝑖,𝑥;𝑠)g(i,x;s)，即已经处理完序列 𝑠s 的长度为 𝑖i 的前缀，且其他状态分量为 𝑥x 时某个量的取值．相应地，内层 DP 的状态转移方程为
𝑔(𝑖,⋅;𝑠)=𝐺(𝑔(𝑖−1,⋅;𝑠),𝑠𝑖).g(i,⋅;s)=G(g(i−1,⋅;s),si).
也就是说，函数 𝑔(𝑖, ⋅;𝑠)g(i,⋅;s) 由之前的函数 𝑔(𝑖 −1, ⋅;𝑠)g(i−1,⋅;s) 和当前的字符 𝑠𝑖si 唯一确定．如果将函数 𝑔(𝑖, ⋅;𝑠)g(i,⋅;s) 看作是自动机的一个状态，那么，内层 DP 的状态转移方程就给出了自动机的一个转移．因此，内层 DP 对应的自动机 (𝑄,Σ,𝛿,𝑞0,𝐹)(Q,Σ,δ,q0,F) 结构如下：
- 状态集合 𝑄Q 就是所有可能的 𝑠 ∈Σ𝑛s∈Σn 和 𝑖 =0,1,⋯,𝑛i=0,1,⋯,n 对应的函数 𝑔(𝑖, ⋅;𝑠)g(i,⋅;s) 的集合；
- 转移函数 𝛿 :𝑄 ×Σ →𝑄δ:Q×Σ→Q 就是内层 DP 的状态转移方程中的 𝐺G；
- 起始状态 𝑞0q0 通常是显然的，即内层 DP 的初始状态；
- 接受状态集合 𝐹F 就对应着所有的合法序列 𝑠 ∈𝐴s∈A．
函数 𝑔(𝑖, ⋅;𝑠)g(i,⋅;s) 本身可能相当复杂，因此，在处理具体问题时，通常需要进行 状态压缩 或结合 DFA 最小化的技巧来压缩状态空间．这也是 DP 套 DP 相较于暴力 DP 能够显著降低时空复杂度的主要原因．
将内层 DP 抽象为 DFA 后，就可以在这个 DFA 上设计一个新的 DP 用于求解原问题，即外层 DP．为方便表述，以简单的计数问题为例．外层 DP 的状态函数定义为 𝑓(𝑖,𝑞)f(i,q)，即处理到长度为 𝑖i 的前缀时，到达 DFA 中状态 𝑞 ∈𝑄q∈Q 的前缀的数目．它的状态转移方程为
𝑓(𝑖,𝑞)=∑𝑐∈Σ∑𝑞′∈𝑄:𝛿(𝑞′,𝑐)=𝑞𝑓(𝑖−1,𝑞′).f(i,q)=∑c∈Σ∑q′∈Q:δ(q′,c)=qf(i−1,q′).
起始状态当然是 𝑓(0,𝑞0)f(0,q0)，而最终要求的答案通常可以根据 {𝑓(𝑛,𝑞) :𝑞 ∈𝐹}{f(n,q):q∈F} 简单计算得到．外层 DP 实际上是 DAG 上 DP 的特殊情形．
例题
接下来的两个例题会详细说明 DP 套 DP 的一般做法．
例一
给定一个字符集为 ACGT 的字符串 𝑆S，且 |𝑆| ≤15|S|≤15．对于每个 0 ≤𝑖 ≤|𝑆|0≤i≤|S|，求有多少个长度为 𝑚m，字符集 ACGT 的字符串 𝑇T，满足它与 𝑆S 的最长公共子序列长度为 𝑖i．
题解
我们首先会想到一个 DP：设 𝑓𝑖,𝑗fi,j 表示长度为 𝑖i 的 𝑇T 中，和 𝑆S 的最长公共子序列的长度为 𝑗j 的方案数．但是这样无法转移，我们发现主要的问题是，我们不知道这个最长公共子序列对应的是哪些字符．
考虑朴素求最长公共子序列的过程．设 𝑔𝑖,𝑗gi,j 表示 𝑇T 的前 𝑖i 位和 𝑆S 的前 𝑗j 位，它们的最长公共子序列的长度，就有
𝑔𝑖,𝑗=max{𝑔𝑖−1,𝑗,𝑔𝑖,𝑗−1,𝑔𝑖−1,𝑗−1+[𝑇𝑖=𝑆𝑗]}.gi,j=max{gi−1,j,gi,j−1,gi−1,j−1+[Ti=Sj]}.
我们发现，对于一个 𝑖i，只需要记录 𝑔𝑖gi 这个一维数组每一位的值，就能准确维护当前 𝑆S 与 𝑇T 前 𝑖i 位最长公共子序列的状态．因为 𝑆S 长度只有 1515，我们发现这个思想是可行的．
于是重新设状态 𝑓𝑖,𝑥fi,x 表示对于长度为 𝑖i 的 𝑇T，与 𝑆S 的 DP 数组（就是 𝑔𝑖gi）状态为 𝑥x 的方案数．这个 DP 看起来状态数很多，然而我们发现 𝑔𝑖,𝑗 −𝑔𝑖,𝑗−1 ∈{0,1}gi,j−gi,j−1∈{0,1}，就可以维护 𝑔𝑖gi 的差分数组，状态数是 2|𝑆|2|S| 的．
现在思考怎么转移．容易发现，如果我们知道了 𝑔𝑖gi 这个数组，也知道了 𝑇𝑖+1Ti+1，就能通过朴素 LCS 转移（即前文的 DP 方程）求出 𝑔𝑖+1gi+1．于是朴素的 LCS 就成为了帮助 𝑓f 转移的内层 DP．
因此，我们枚举 𝑇𝑖+1Ti+1，计算出 𝑥x 转移后的状态 𝑥′x′，再将 𝑓𝑖+1,𝑥′fi+1,x′ 加上 𝑓𝑖,𝑥fi,x 就可以完成外层 DP 的状态转移．最后，我们记录 𝑎𝑛𝑠𝑖ansi 为 LCS 长度为 𝑖i 的答案，枚举每个状态 𝑆S，𝑎𝑛𝑠popcount(𝑆)anspopcount(S) 加上 𝑓𝑚,𝑆fm,S 即可．
参考代码
---|---
### 例二
[[ZJOI2019] 麻将](https://loj.ac/p/3042)
假设麻将牌有 𝑛n 种大小的牌，每种大小有 44 张牌．定义面子为三张相邻大小的麻将牌 𝑖,𝑖 +1,𝑖 +2i,i+1,i+2（顺子）或三种相同大小的麻将牌 𝑖,𝑖,𝑖i,i,i（刻子），对子为两张相同大小的麻将牌 𝑖,𝑖i,i．定义一个麻将牌的序列是胡的，当且仅当它（看作多重集合）可以拆成四个面子和一个对子，或者七个不同的对子．给定 1313 张麻将牌，问期望再摸多少张牌可以满足存在一个胡牌的子序列的条件．
题解
首先，对于一副牌，我们只需考虑每种牌的数量，而不必关心它们的顺序．因此，对于任何一副牌的任意前缀，我们都可以将它转化为一个长度为 𝑛n，每个位置上为 0 ∼40∼4 的序列．初始时，第 𝑖i 张牌的数量为 𝑎𝑖ai，就相当于限制了序列中第 𝑖i 个数字 𝑥𝑖xi 的取值为 [𝑎𝑖,4][ai,4] 内的整数．注意，转化后的序列没有考虑摸牌的顺序，但是题目中的麻将牌的序列是考虑顺序的．
设 𝑋X 表示可以胡牌的最小摸牌次数．直接计算期望 𝐄[𝑋]E[X] 较为困难，可以考虑进行如下转化．设 ℎ𝑖hi 表示摸了 𝑖i 张牌后 **没有胡** 的序列数．因为它对应的麻将牌序列中，这 𝑖i 张牌必然排在剩下的 (4𝑛 −13 −𝑖)(4n−13−i) 张牌前方，但是这 𝑖i 张牌和剩下的 (4𝑛 −13 −𝑖)(4n−13−i) 张牌的顺序是任意的，所以，只摸前 𝑖i 张牌无法胡牌的麻将牌序列的数目就是
ℎ𝑖⋅𝑖!(4𝑛−13−𝑖)!.hi⋅i!(4n−13−i)!.
因为麻将牌序列的总数为 (4𝑛 −13)!(4n−13)!，所以，只摸前 𝑖i 张牌无法胡牌的概率为
𝐏[𝑋>𝑖]=ℎ𝑖⋅𝑖!(4𝑛−13−𝑖)!(4𝑛−13)!.P[X>i]=hi⋅i!(4n−13−i)!(4n−13)!.
利用尾求和公式，就可以得到所求期望
𝐄[𝑋]=∞∑𝑖=0𝐏[𝑋>𝑖]=1+4𝑛−13∑𝑖=1ℎ𝑖⋅𝑖!(4𝑛−13−𝑖)!(4𝑛−13)!.E[X]=∑i=0∞P[X>i]=1+∑i=14n−13hi⋅i!(4n−13−i)!(4n−13)!.
至此，问题转化为如何计算 ℎ𝑖hi．我们采用 DP 套 DP 的方法来解决这一问题．
首先，考虑内层 DP，也就是要用动态规划判断一个（转化后的）序列是否对应一副能胡的牌．七对子的情形较为容易，重点讨论第一种胡牌的形式．为此，设 𝑔0/1,𝑖,𝑗,𝑘g0/1,i,j,k 表示处理完前 𝑖i 种牌，还剩 𝑗j 组 (𝑖 −1,𝑖)(i−1,i) 以及 𝑘k 张 𝑖i，且存在/不存在对子（即 0/10/1）时最多的面子数．如果对于一个序列进行 DP，最后得到的 𝑔1,𝑛g1,n 中包括一个大于等于 44 的数字，那么这个序列就是能胡的．
这个 DP 的状态转移较为复杂．我们分两步讨论．第一步，考虑 𝑔0/1,𝑖g0/1,i 的转移．这相当于说，如果要向现在的牌型中，添加 𝑥𝑖xi 张大小为 𝑖i 的牌，但是不组成新的对子时，面子数如何转移．显然，如果希望在添加 𝑥𝑖xi 张大小为 𝑖i 的牌后，要得到 ℓℓ 个顺子，𝑗j 个 (𝑖 −1,𝑖)(i−1,i) 和 𝑘k 个单独的 𝑖i，那么，就应该从 (𝑔0/1,𝑖−1)ℓ,𝑗(g0/1,i−1)ℓ,j 中转移过来（这里的选择最大程度避免了浪费），并将剩余的牌 (𝑥𝑖 −ℓ −𝑗 −𝑘)(xi−ℓ−j−k) 用于组成尽可能多的刻子．穷举所有的可能性，就得到如下转移方程：
˜𝐺(𝑔0/1,𝑖−1,𝑥𝑖)𝑗,𝑘=max{(𝑔0/1,𝑖−1)ℓ,𝑗+ℓ+⌊𝑥𝑖−ℓ−𝑗−𝑘3⌋:ℓ+𝑗+𝑘≤𝑥𝑖}.G~(g0/1,i−1,xi)j,k=max{(g0/1,i−1)ℓ,j+ℓ+⌊xi−ℓ−j−k3⌋:ℓ+j+k≤xi}.
第二步，再考虑需要组成对子的情形．加入 𝑥𝑖xi 张大小为 𝑖i 的牌时，有如下三种转移：
* 将 𝑔0,𝑖−1g0,i−1 加 𝑥𝑖xi 张牌转移到 𝑔0,𝑖g0,i；
* 将 𝑔1,𝑖−1g1,i−1 加 𝑥𝑖xi 张牌转移到 𝑔1,𝑖g1,i；
* 若 𝑥𝑖 ≥2xi≥2，将 𝑔0,𝑖−1g0,i−1 加 𝑥𝑖 −2xi−2 张牌转移到 𝑔1,𝑖g1,i．
由此，就得到了从 𝑔𝑖−1gi−1 添加 𝑥𝑖xi 张牌得到 𝑔𝑖gi 的全部转移．
解决了内层 DP 的状态转移，就可以构建 **胡牌自动机** ．自动机的转移就是上述内层 DP 的转移，还需要考虑如何表示自动机的每个状态．每个状态都对应 𝑔𝑖gi 的一种可能的取值．它有三个维度 (0/1,𝑗,𝑘)(0/1,j,k)．因为 𝑗j 和 𝑘k 对应的维度中保留的 (𝑖 −1,𝑖)(i−1,i) 和 𝑖i 都是用于将来组成顺子的，而三个相同顺子总是可以重组为三个刻子，所以，只需要考虑组成不超过 22 个相同顺子的需求就行，每种牌型也就只要保留不超过 22 个，即 𝑗,𝑘 ∈{0,1,2}j,k∈{0,1,2}．因此，𝑔𝑖gi 可以表示为一个 2 ×3 ×32×3×3 的数组．另外，为了维护七对子的胡牌牌型，还需要为每个状态添加一个计数器，用于表示当前最多可组成的对子数目．
数组 𝑔𝑖gi 中每个元素的取值范围可能是 { −∞} ∪𝐍{−∞}∪N，但是，因为面子数目大于等于 44 都是胡牌，所以，可以限制每个元素取值不超过 44．由于胡牌序列再添加任何牌都是胡牌序列，所以，可以利用 DFA 最小化的思想，将全体胡牌状态压缩为一个状态．因此，对于非胡牌状态，实际上每个位置的取值只要考虑 { −∞} ∪{0,1,2,3}{−∞}∪{0,1,2,3} 就可以了．实现时，−∞−∞ 用 −1−1 表示．
尽管如此，所有可能的状态依然相当地多，共有 1 +7 ×5181+7×518 种．穷举它们并不现实．实际上，绝大多数这些可能性都不会真的出现在一个胡牌自动机中．为了避免考虑实际不存在的状态，可以利用 BFS 的思想，从初始状态开始，一步一步扩展状态，直到胡牌状态处停止．这样得到的自动机中有 𝑁 =2092N=2092 个状态．
最后，考虑如何在胡牌自动机上 DP（即外层 DP）．设 𝑓𝑖,𝑗,𝑘fi,j,k 表示处理到第 𝑖i 张牌，共摸了 𝑗j 张牌，走到了胡牌自动机上的 𝑘k 号状态的序列数．转移时，枚举摸牌数 0 ≤𝑡 ≤4 −𝑎𝑖0≤t≤4−ai，其中 𝑎𝑖ai 为初始 1313 张牌中用掉的 𝑖i 的张数，将之前的序列数乘以 4 −𝑎𝑖4−ai 张牌中选 𝑡t 张牌的方案数 (4−𝑎𝑖𝑡)(4−ait)，再累加到一起．形式化地，有：
𝑓𝑖+1,𝑗+𝑡,𝑘′=4−𝑎𝑖∑𝑡=0(4−𝑎𝑖𝑡)𝑓𝑖,𝑗,𝑘.fi+1,j+t,k′=∑t=04−ai(4−ait)fi,j,k.
其中，𝑘′ =𝛿(𝑘,𝑎𝑖 +𝑡)k′=δ(k,ai+t)，表示向自动机的状态 𝑘k 中加入 𝑎𝑖 +𝑡ai+t 张牌后的状态．外层 DP 结束后，就可以计算出摸了 𝑖i 张牌仍然没有胡牌的序列数目，即
ℎ𝑖=𝑁∑𝑗=1𝑓𝑛,𝑖,𝑗.hi=∑j=1Nfn,i,j.
代入前文所述表达式，就可以得到所要求的期望．
参考代码
---|---
习题
- CF979E Kuro and Topological Parity
- [[TJOI2018] 游园会](https://loj.ac/p/2575)
- [[NOI2022] 移除石子](https://loj.ac/p/3848)
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：c-forrest, Hope666666, Tiphereth-A, ZnPdCo 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用