计数 DP

计数 DP 是一种利用类似 DP 的记忆化搜索方法（与在狭义上的 DP，即最优化问题有一定区别），用于解决计数（以及求和）问题。

基础

基本思想

计数问题一般指求一个集合 \(S\) 的大小，在 OI 中，\(S\) 的大小有时会达到 \(\Theta(n^n)\) 甚至 \(\Theta(2^{n!})\) 的级别（当然，一般会对某一个固定的数取模），其中 \(n\) 是问题规模，所以我们不能逐一求出 \(S\) 的元素。

如果我们能够将 \(S\) 分成若干无交的子集，那么 \(S\) 的元素个数就等于这些部分的元素个数的和。如果这些子集的计数恰好与原问题类似，那么我们就可以通过类似动态规划的方法来解决。

例题

例题

给定一个正整数 \(n\)，求有多少个把 \(n\) 划分成 \(k\) 个正整数的和的方案，位置调换视为不同的划分方案。

需集合 \(S_{n,k}\) 为形如 \((a_1, \dots, a_k)\) 的正整数组组成的集合，其中 \(a_1 + \dots + a_k = n\)。如果 \(a_k\) 固定，则有如下推导：因为 \(a_1 + a_2 + \dots + a_{k-1} + a_k = n\)，所以 \(a_1 + a_2 + \dots + a_{k-1} = n - a_k\)。根据 \(S_{n,k}\) 的定义，\((a_1, a_2, \dots, a_{k-1}) \in S_{n - a_k, k - 1}\)。

由于 \(a_1, a_2, \dots, a_k\) 是正整数，所以 \(a_k\) 的取值范围是 \([1, n - k + 1] \cap \mathbb Z\)。因此，\(S_{n,k}\) 可以按照 \(a_k\) 被划分，分成 \(n - k + 1\) 个子集，其中当 \(a_k = i\) 时，这个子集为：

\[ \{(L, i) \mid L \in S_{n-i,k-1}\}. \]

这个子集的元素个数显然等于 \(S_{n-i,k-1}\)，由于 \(i\) 的不同，这些子集两两无交。所以：

\[ |S_{n,k}| = \sum_{i=1}^{n-k+1} |S_{n-i,k-1}|. \]

这样我们就可以使用类似 DP 的方法处理它：设 \(f_{n,k}\) 为 \(|S_{n,k}|\)，则有状态转移方程：

\[ f_{n,k} = \sum_{i=1}^{n-k+1} f_{n-i,k-1}. \]

这样就可以使用 DP 的方法求解了。

与最优化 DP 的异同

可以发现，计数 DP 和最优化 DP 都是在一个范围 \(\Omega\) 内求一个值（大小值、最优值），这个值通过将 \(\Omega\) 中的所有元素做一次处理，再对处理值做一次整合得到。

例如，对于 0-1 背包问题，\(\Omega\) 中的元素为背包内的所有物品组成的集合，对于 \(\Omega\) 中的一个方案 \(S\)，我们对 \(S\) 做一次处理，处理得到的结果 \(w(S)\) 为 \(S\) 中物品的总价值，对所有得到的处理值，我们取最大值，得到问题的答案。

对于计数问题，\(\Omega\) 中的元素为要计算元素个数的集合 \(S\)，它的处理是把所有的 \(S\) 中元素变为 \(1\)，然后将这些 \(1\) 通过加法的方式汇总起来，因为每一个 \(S\) 中元素都对应一个 \(1\)，所以这样得到的值就是 \(S\) 中元素个数。

当汇总操作为最大/最小值时，我们可以将 \(\Omega\) 分成任意若干个部分，只需这些部分的并为 \(\Omega\) 即可，无需无交的条件。而计数问题由于不满足这个条件，所以我们需要将 \(\Omega\) 分成若干个部分，这些部分两两无交，这就是与最优化 DP 的区别。

例题

例题

给定一个正整数 \(n\)，求有多少个把 \(n\) 划分成任意多个正整数的和的方案，位置调换视为 相同 的划分方案。

解法 1

需要计算的集合的元素为满足其和为 \(n\) 的正整数多重集。但是这样显然不好推。

若一个多重集 \(T\) 只包含 \(\le M\) 的正整数，且 \(T\) 中所有元素的和为 \(n\)，则称 \(T \in S_{n, M}\)。考虑 \(M\) 出现的个数。可能为 \(k \in \left[0, \left\lfloor \dfrac nM \right\rfloor\right] \cap \mathbb Z\)。于是它可以被转移到 \(S_{n - kM, M - 1}\)。求和一下即可。复杂度是 \(\Theta(n^2 \log n)\)（\(\log\) 来自于 \(k\) 的范围导致的调和级数）。

但是这样还不够优秀。考虑下面所示的一个例子：

\[ \begin{aligned} f_{8, 3} &= {\color{red}f_{8, 2} + f_{5, 2} + f_{2, 2}} \\ f_{9, 3} &= {\color{blue}f_{9, 2} + f_{6, 2} + f_{3, 2} + f_{0, 2}} \\ f_{10, 3} &= {\color{green}f_{10, 2} + f_{7, 2} + f_{4, 2} + f_{1, 2}}\\ f_{11, 3} &= f_{11, 2} + {\color{red}f_{8, 2} + f_{5, 2} + f_{2, 2}}\\ f_{12, 3} &= f_{12, 2} + {\color{blue}f_{9, 2} + f_{6, 2} + f_{3, 2} + f_{0, 2}}\\ f_{13, 3} &= f_{13, 2} + {\color{green}f_{10, 2} + f_{7, 2} + f_{4, 2} + f_{1, 2}}\\ \end{aligned} \]

等量代换得 \(f_{11, 3} = f_{11, 2} + f_{8, 3}\)，\(f_{12, 3} = f_{12, 2} + f_{9, 3}\)，\(f_{13, 3} = f_{13, 2} + f_{10, 3}\)。同理我们可以得到一个通用的状态转移方程：

\[ f_{n, M} = f_{n, M - 1} + \begin{cases} f_{n - M, M} & n \ge M, \\ 0 & \text{otherwise}. \end{cases} \]

此时，时间复杂度为 \(\Theta(n^2)\)。

解法 2

考虑到某一个正整数组成的多重集 \(T\) 必然可以通过「将 \(T\) 中每一个元素自增」、「在 \(T\) 中加一个值为 \(1\) 的元素」两个操作得到，并且不同的操作序列得到的结果是不同的。

这样对 \(T\) 的转移可以变为对操作序列的转移。考虑将 \(n\) 划分成 \(m\) 个数的操作序列（所有的这些操作序列记作 \(B_{n,m}\)）中的最后一次操作，如果是 \(1\) 操作，那么不会增加数，但是 \(\sum T\) 增加了 \(m\)。为了使最终的 \(\sum T = n\)，原来的 \(T\)（记作 \(T'\)）的和需要为 \(n-m\)。所以 \(B_{n,m} \to B_{n-m,m}\)；如果是 \(2\) 操作，那么会增加一个数，\(\sum T\) 增加了 \(1\)。所以 \(B_{n,m} \to B_{n-1,m-1}\)。

这样做的时间复杂度依旧是 \(\Theta(n^2)\)。

解法 3

考虑将 \(T\) 分为大于 \(\sqrt n\) 的部分 \(T_1\) 和小于等于 \(\sqrt n\) 的部分 \(T_2\)。\(T_2\) 可以使用解法 1 求出，而 \(T_1\) 的数量可以通过略微修改解法 2 求出：考虑将两个操作变为「将 \(T_1\) 中每一个元素自增」、「在 \(T_1\) 中加一个值为 \(\lfloor \sqrt n \rfloor + 1\) 的元素」。容易列出状态转移方程。

将 \(n\) 拆为 \(A\) 和 \(B\) 两部分。枚举其中一个即可得出另一个。将满足 \(\sum T_1 = A\) 的 \(T_1\) 个数和 \(\sum T_2 = B\) 的 \(T_2\) 个数求出，乘起来，对所有的 \(A\) 求和便是最终结果。

由于在计算 \(T_1\) 个数的过程中，\(M \le \sqrt n\)，所以我们利用解法 1 计算 \(T_1\) 的时间复杂度为 \(\Theta(n^{3/2})\)。同样地，由于在计算 \(T_2\) 个数的过程中，\(|T_2| \le \dfrac{\sum T_2}{\sqrt n} \le \dfrac{n}{\sqrt n} = \sqrt n\)，所以我们利用解法 2 计算 \(T_2\) 的时间复杂度也是 \(\Theta(n^{3/2})\)。所以总时间复杂度为 \(\Theta(n^{3/2})\)。