计数DP

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

基础

基本思想

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

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

例题

需集合 $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 的区别。

例题：