DP新解与DP套DP技术

先简单介绍一下理解DP的另一个角度.

假设我们要处理一个问题,无论是最优化或是计数问题.搜索的策略是,枚举所有可能的情况,因此复杂度通常为指数级;DP的策略是,将满足某种”共同特征”的所有方案看作一个整体状态,只保留这个整体的最优值/方案数/概率期望 等信息,并通过已知状态推出其他状态,若这种”共同特征”确定得当,则复杂度便可降为多项式级别.

譬如在背包问题中,对于体积和为$x$的所有方案,我们只保存其最优值.

此外,这种理解也符合计数DP也算DP,而单纯的斐波那契数列递推等不算DP这个预期.

下面谈一谈DP套DP技术.这里以「ZJOI2019」麻将 为例.

首先,对所有可能的麻将排列,我们只关注麻将的数量,以及这些麻将是否(存在一个子集)能胡.但是,发现对于两组麻将,很难确定一个”共同特征”.

这是因为,判定麻将是否能胡,并不是极为容易.事实上仅仅是判定,我们就需要一个DP.

比如,设$f(i,x,y,0/1)$表示考虑到第$i$种牌,第$i-1$种牌还剩$x$张,第$i$种牌还剩$y$张,且有/没有 对子时最大的面子数量,$g(i)$表示考虑到第$i$张牌,不同的对子数量.或者也可以设$f(i,x,y,0/1)$表示考虑到第$i$张牌,且$i-1$开头的顺子有$x$个,$i$开头的顺子有$y$个,且有/没有 对子时最大的面子数量,$g(i)$同上.最后若存在一种方案满足有对子且面子至少4个,或者有至少七对对子即可胡. 两种DP都可行,只有常数上的差距.

首先忽略$i$,对后续转移没有影响;对于两组麻将$P,Q$,若$\forall(x,y,k),f_P(x,y,k)=f_Q(x,y,k),g_p=g_Q$($f_P$表示对$P$做上述DP得到的结果,$f_Q$同理),那么无论之后接上什么麻将,之后的DP值都相同,是否胡牌当然也相同了.那么可以尝试,将这个DP的内容,做为一个”共同特征”.可惜的是这样做复杂度难以接受:可能的DP值数量太多,作为状态会导致复杂度无法接受.

我们再从另外一个视角看DP.设给定一个输入序列$P$,求得$f_P$.现在要在$P$后加入一个元素$x$,求得$f_{P+x}$.其实就是从一个状态走到了另一个状态,宏观上看恰如DFA(DFA即确定性有限状态自动机,不熟悉的读者可参考网上资料或参考文献1)上从一个点走到另一个点.说的详细些就是,对这个DP,我们有一个DFA,DP每一种可能的状态都对应DFA上的一个点,DP的转移对应DFA的边,对于给定的输入序列$P$,就是从DFA的起始状态开始走,经过一条链最终走到一个节点,其代表的状态就是我们所求.

对这样一个判断是否能胡的DP,我们也建立一个DFA.所有可能的麻将序列都对应DFA上一条链.另外维护一下每个点能不能胡.这样做的意义在于,虽然可能的麻将序列,可能的DP值数量很多,但若钦定$f$的值不超过4,$g$的值不超过7,这个DFA的节点却比较少:根据实现方法不同,有1500~4000个点(但似乎用第一种DP可能会有9000+的点?)

于是,我们可以直接用DFA的点来表示一个DP状态了.最后求答案的DP是,$f(i,j,p)$表示考虑前$i$种牌,选了$j$张,对应在DFA的节点$p$时的方案数.转移时枚举$i$种选了几张即可(注意同种牌中也是有编号的,还要乘上选出几张的组合数).将第$j$张牌才胡(贡献应为$j$)转化为$1…j$张牌都有1的贡献,答案为:
$$\frac{\sum_{j=14}^{4n}\sum_{p\not\in Win}f(n,j,p)(j-13)!(n-j)!}{(4n-13)!}$$
时间复杂度$O(n^2m),m$为DFA的节点数.这种技术称为DP套DP技术.

参考代码:https://loj.ac/s/1115773

此外,徐哲安学长指出,通过DFA最小化技术,可以将DFA缩小至只有200~300个点,详情可见其论文(参考文献1)

参考文献:

1. 徐哲安，浅谈有限状态自动机及其应用,2021年集训队论文