跳转至

# 计数 DP

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

## 基础

### 基本思想

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

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

### 例题

例题

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

需集合 𝑆 𝑛,𝑘 S n,k 为形如 (𝑎 1,…,𝑎 𝑘)(a 1,…,a k) 的正整数组组成的集合，其中 𝑎 1 +⋯ +𝑎 𝑘 =𝑛 a 1+⋯+a k=n．如果 𝑎 𝑘 a k 固定，则有如下推导：因为 𝑎 1 +𝑎 2 +⋯ +𝑎 𝑘−1 +𝑎 𝑘 =𝑛 a 1+a 2+⋯+a k−1+a k=n，所以 𝑎 1 +𝑎 2 +⋯ +𝑎 𝑘−1 =𝑛 −𝑎 𝑘 a 1+a 2+⋯+a k−1=n−a k．根据 𝑆 𝑛,𝑘 S n,k 的定义，(𝑎 1,𝑎 2,…,𝑎 𝑘−1) ∈𝑆 𝑛−𝑎 𝑘,𝑘−1(a 1,a 2,…,a k−1)∈S n−a k,k−1．

由于 𝑎 1,𝑎 2,…,𝑎 𝑘 a 1,a 2,…,a k 是正整数，所以 𝑎 𝑘 a k 的取值范围是 [1,𝑛 −𝑘 +1] ∩ℤ[1,n−k+1]∩Z．因此，𝑆 𝑛,𝑘 S n,k 可以按照 𝑎 𝑘 a k 被划分，分成 𝑛 −𝑘 +1 n−k+1 个子集，其中当 𝑎 𝑘 =𝑖 a k=i 时，这个子集为：

{(𝐿,𝑖)∣𝐿∈𝑆 𝑛−𝑖,𝑘−1}.{(L,i)∣L∈S n−i,k−1}.

这个子集的元素个数显然等于 𝑆 𝑛−𝑖,𝑘−1 S n−i,k−1，由于 𝑖 i 的不同，这些子集两两无交．所以：

|𝑆 𝑛,𝑘|=𝑛−𝑘+1∑𝑖=1|𝑆 𝑛−𝑖,𝑘−1|.|S n,k|=∑i=1 n−k+1|S n−i,k−1|.

这样我们就可以使用类似 DP 的方法处理它：设 𝑓 𝑛,𝑘 f n,k 为 |𝑆 𝑛,𝑘||S n,k|，则有状态转移方程：

𝑓 𝑛,𝑘=𝑛−𝑘+1∑𝑖=1 𝑓 𝑛−𝑖,𝑘−1.f n,k=∑i=1 n−k+1 f n−i,k−1.

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

### 与最优化 DP 的异同

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

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

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

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

## 例题

例题

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

### 解法 1

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

若一个多重集 𝑇 T 只包含 ≤𝑀≤M 的正整数，且 𝑇 T 中所有元素的和为 𝑛 n，则称 𝑇 ∈𝑆 𝑛,𝑀 T∈S n,M．考虑 𝑀 M 出现的个数．可能为 𝑘 ∈[0,⌊𝑛 𝑀⌋] ∩ℤ k∈[0,⌊n M⌋]∩Z．于是它可以被转移到 𝑆 𝑛−𝑘 𝑀,𝑀−1 S n−k M,M−1．求和一下即可．复杂度是 Θ(𝑛 2 l o g⁡𝑛)Θ(n 2 log⁡n)（l o g log 来自于 𝑘 k 的范围导致的调和级数）．

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

𝑓 8,3=𝑓 8,2+𝑓 5,2+𝑓 2,2 𝑓 9,3=𝑓 9,2+𝑓 6,2+𝑓 3,2+𝑓 0,2 𝑓 1 0,3=𝑓 1 0,2+𝑓 7,2+𝑓 4,2+𝑓 1,2 𝑓 1 1,3=𝑓 1 1,2+𝑓 8,2+𝑓 5,2+𝑓 2,2 𝑓 1 2,3=𝑓 1 2,2+𝑓 9,2+𝑓 6,2+𝑓 3,2+𝑓 0,2 𝑓 1 3,3=𝑓 1 3,2+𝑓 1 0,2+𝑓 7,2+𝑓 4,2+𝑓 1,2 f 8,3=f 8,2+f 5,2+f 2,2 f 9,3=f 9,2+f 6,2+f 3,2+f 0,2 f 10,3=f 10,2+f 7,2+f 4,2+f 1,2 f 11,3=f 11,2+f 8,2+f 5,2+f 2,2 f 12,3=f 12,2+f 9,2+f 6,2+f 3,2+f 0,2 f 13,3=f 13,2+f 10,2+f 7,2+f 4,2+f 1,2

等量代换得 𝑓 1 1,3 =𝑓 1 1,2 +𝑓 8,3 f 11,3=f 11,2+f 8,3，𝑓 1 2,3 =𝑓 1 2,2 +𝑓 9,3 f 12,3=f 12,2+f 9,3，𝑓 1 3,3 =𝑓 1 3,2 +𝑓 1 0,3 f 13,3=f 13,2+f 10,3．同理我们可以得到一个通用的状态转移方程：

𝑓 𝑛,𝑀=𝑓 𝑛,𝑀−1+{𝑓 𝑛−𝑀,𝑀 𝑛≥𝑀,0 o t h e r w i s e.f n,M=f n,M−1+{f n−M,M n≥M,0 otherwise.

此时，时间复杂度为 Θ(𝑛 2)Θ(n 2)．

### 解法 2

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

这样对 𝑇 T 的转移可以变为对操作序列的转移．考虑将 𝑛 n 划分成 𝑚 m 个数的操作序列（所有的这些操作序列记作 𝐵 𝑛,𝑚 B n,m）中的最后一次操作，如果是 1 1 操作，那么不会增加数，但是 ∑𝑇∑T 增加了 𝑚 m．为了使最终的 ∑𝑇 =𝑛∑T=n，原来的 𝑇 T（记作 𝑇′T′）的和需要为 𝑛 −𝑚 n−m．所以 𝐵 𝑛,𝑚 →𝐵 𝑛−𝑚,𝑚 B n,m→B n−m,m；如果是 2 2 操作，那么会增加一个数，∑𝑇∑T 增加了 1 1．所以 𝐵 𝑛,𝑚 →𝐵 𝑛−1,𝑚−1 B n,m→B n−1,m−1．

这样做的时间复杂度依旧是 Θ(𝑛 2)Θ(n 2)．

### 解法 3

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

将 𝑛 n 拆为 𝐴 A 和 𝐵 B 两部分．枚举其中一个即可得出另一个．将满足 ∑𝑇 1 =𝐴∑T 1=A 的 𝑇 1 T 1 个数和 ∑𝑇 2 =𝐵∑T 2=B 的 𝑇 2 T 2 个数求出，乘起来，对所有的 𝐴 A 求和便是最终结果．

由于在计算 𝑇 1 T 1 个数的过程中，𝑀 ≤√𝑛 M≤n，所以我们利用解法 1 计算 𝑇 1 T 1 的时间复杂度为 Θ(𝑛 3/2)Θ(n 3/2)．同样地，由于在计算 𝑇 2 T 2 个数的过程中，|𝑇 2| ≤∑𝑇 2√𝑛 ≤𝑛√𝑛 =√𝑛|T 2|≤∑T 2 n≤n n=n，所以我们利用解法 2 计算 𝑇 2 T 2 的时间复杂度也是 Θ(𝑛 3/2)Θ(n 3/2)．所以总时间复杂度为 Θ(𝑛 3/2)Θ(n 3/2)．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Tiphereth-A, FFjet, Ir1d, OIer1048576
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用