计数 DP
计数 DP 是一种利用类似 DP 的记忆化搜索方法（与在狭义上的 DP，即最优化问题有一定区别），用于解决计数（以及求和）问题．
基础
基本思想
计数问题一般指求一个集合 𝑆S
的大小，在 OI 中，𝑆S 的大小有时会达到 Θ(𝑛𝑛)Θ(nn) 甚至 Θ(2𝑛!)Θ(2n!) 的级别（当然，一般会对某一个固定的数取模），其中 𝑛n 是问题规模，所以我们不能逐一求出 𝑆S 的元素．
如果我们能够将 𝑆S 分成若干无交的子集，那么 𝑆S 的元素个数就等于这些部分的元素个数的和．如果这些子集的计数恰好与原问题类似，那么我们就可以通过类似动态规划的方法来解决．
例题
例题
给定一个正整数 𝑛n，求有多少个把 𝑛n 划分成 𝑘k 个正整数的和的方案，位置调换视为不同的划分方案．
需集合 𝑆𝑛,𝑘Sn,k 为形如 (𝑎1,…,𝑎𝑘)(a1,…,ak) 的正整数组组成的集合，其中 𝑎1 +⋯ +𝑎𝑘 =𝑛a1+⋯+ak=n．如果 𝑎𝑘ak 固定，则有如下推导：因为 𝑎1 +𝑎2 +⋯ +𝑎𝑘−1 +𝑎𝑘 =𝑛a1+a2+⋯+ak−1+ak=n，所以 𝑎1 +𝑎2 +⋯ +𝑎𝑘−1 =𝑛 −𝑎𝑘a1+a2+⋯+ak−1=n−ak．根据 𝑆𝑛,𝑘Sn,k 的定义，(𝑎1,𝑎2,…,𝑎𝑘−1) ∈𝑆𝑛−𝑎𝑘,𝑘−1(a1,a2,…,ak−1)∈Sn−ak,k−1．
由于 𝑎1,𝑎2,…,𝑎𝑘a1,a2,…,ak 是正整数，所以 𝑎𝑘ak 的取值范围是 [1,𝑛 −𝑘 +1] ∩ℤ[1,n−k+1]∩Z．因此，𝑆𝑛,𝑘Sn,k 可以按照 𝑎𝑘ak 被划分，分成 𝑛 −𝑘 +1n−k+1 个子集，其中当 𝑎𝑘 =𝑖ak=i 时，这个子集为：
{(𝐿,𝑖)∣𝐿∈𝑆𝑛−𝑖,𝑘−1}.{(L,i)∣L∈Sn−i,k−1}.
这个子集的元素个数显然等于 𝑆𝑛−𝑖,𝑘−1Sn−i,k−1，由于 𝑖i 的不同，这些子集两两无交．所以：
|𝑆𝑛,𝑘|=𝑛−𝑘+1∑𝑖=1|𝑆𝑛−𝑖,𝑘−1|.|Sn,k|=∑i=1n−k+1|Sn−i,k−1|.
这样我们就可以使用类似 DP 的方法处理它：设 𝑓𝑛,𝑘fn,k 为 |𝑆𝑛,𝑘||Sn,k|，则有状态转移方程：
𝑓𝑛,𝑘=𝑛−𝑘+1∑𝑖=1𝑓𝑛−𝑖,𝑘−1.fn,k=∑i=1n−k+1fn−i,k−1.
这样就可以使用 DP 的方法求解了．
与最优化 DP 的异同
可以发现，计数 DP 和最优化 DP 都是在一个范围 ΩΩ 内求一个值（大小值、最优值），这个值通过将 ΩΩ 中的所有元素做一次处理，再对处理值做一次整合得到．
例如，对于 0-1 背包问题，ΩΩ 中的元素为背包内的所有物品组成的集合，对于 ΩΩ 中的一个方案 𝑆S，我们对 𝑆S 做一次处理，处理得到的结果 𝑤(𝑆)w(S) 为 𝑆S 中物品的总价值，对所有得到的处理值，我们取最大值，得到问题的答案．
对于计数问题，ΩΩ 中的元素为要计算元素个数的集合 𝑆S，它的处理是把所有的 𝑆S 中元素变为 11，然后将这些 11 通过加法的方式汇总起来，因为每一个 𝑆S 中元素都对应一个 11，所以这样得到的值就是 𝑆S 中元素个数．
当汇总操作为最大/最小值时，我们可以将 ΩΩ 分成任意若干个部分，只需这些部分的并为 ΩΩ 即可，无需无交的条件．而计数问题由于不满足这个条件，所以我们需要将 ΩΩ 分成若干个部分，这些部分两两无交，这就是与最优化 DP 的区别．
例题
例题
给定一个正整数 𝑛n，求有多少个把 𝑛n 划分成任意多个正整数的和的方案，位置调换视为 相同 的划分方案．
解法 1
需要计算的集合的元素为满足其和为 𝑛n 的正整数多重集．但是这样显然不好推．
若一个多重集 𝑇T 只包含 ≤𝑀≤M 的正整数，且 𝑇T 中所有元素的和为 𝑛n，则称 𝑇 ∈𝑆𝑛,𝑀T∈Sn,M．考虑 𝑀M 出现的个数．可能为 𝑘 ∈[0,⌊𝑛𝑀⌋] ∩ℤk∈[0,⌊nM⌋]∩Z．于是它可以被转移到 𝑆𝑛−𝑘𝑀,𝑀−1Sn−kM,M−1．求和一下即可．复杂度是 Θ(𝑛2log𝑛)Θ(n2logn)（loglog 来自于 𝑘k 的范围导致的调和级数）．
但是这样还不够优秀．考虑下面所示的一个例子：
𝑓8,3=𝑓8,2+𝑓5,2+𝑓2,2𝑓9,3=𝑓9,2+𝑓6,2+𝑓3,2+𝑓0,2𝑓10,3=𝑓10,2+𝑓7,2+𝑓4,2+𝑓1,2𝑓11,3=𝑓11,2+𝑓8,2+𝑓5,2+𝑓2,2𝑓12,3=𝑓12,2+𝑓9,2+𝑓6,2+𝑓3,2+𝑓0,2𝑓13,3=𝑓13,2+𝑓10,2+𝑓7,2+𝑓4,2+𝑓1,2f8,3=f8,2+f5,2+f2,2f9,3=f9,2+f6,2+f3,2+f0,2f10,3=f10,2+f7,2+f4,2+f1,2f11,3=f11,2+f8,2+f5,2+f2,2f12,3=f12,2+f9,2+f6,2+f3,2+f0,2f13,3=f13,2+f10,2+f7,2+f4,2+f1,2
等量代换得 𝑓11,3 =𝑓11,2 +𝑓8,3f11,3=f11,2+f8,3，𝑓12,3 =𝑓12,2 +𝑓9,3f12,3=f12,2+f9,3，𝑓13,3 =𝑓13,2 +𝑓10,3f13,3=f13,2+f10,3．同理我们可以得到一个通用的状态转移方程：
𝑓𝑛,𝑀=𝑓𝑛,𝑀−1+{𝑓𝑛−𝑀,𝑀𝑛≥𝑀,0otherwise.fn,M=fn,M−1+{fn−M,Mn≥M,0otherwise.
此时，时间复杂度为 Θ(𝑛2)Θ(n2)．
解法 2
考虑到某一个正整数组成的多重集 𝑇T 必然可以通过「将 𝑇T 中每一个元素自增」、「在 𝑇T 中加一个值为 11 的元素」两个操作得到，并且不同的操作序列得到的结果是不同的．
这样对 𝑇T 的转移可以变为对操作序列的转移．考虑将 𝑛n 划分成 𝑚m 个数的操作序列（所有的这些操作序列记作 𝐵𝑛,𝑚Bn,m）中的最后一次操作，如果是 11 操作，那么不会增加数，但是 ∑𝑇∑T 增加了 𝑚m．为了使最终的 ∑𝑇 =𝑛∑T=n，原来的 𝑇T（记作 𝑇′T′）的和需要为 𝑛 −𝑚n−m．所以 𝐵𝑛,𝑚 →𝐵𝑛−𝑚,𝑚Bn,m→Bn−m,m；如果是 22 操作，那么会增加一个数，∑𝑇∑T 增加了 11．所以 𝐵𝑛,𝑚 →𝐵𝑛−1,𝑚−1Bn,m→Bn−1,m−1．
这样做的时间复杂度依旧是 Θ(𝑛2)Θ(n2)．
解法 3
考虑将 𝑇T 分为大于 √𝑛n 的部分 𝑇1T1 和小于等于 √𝑛n 的部分 𝑇2T2．𝑇2T2 可以使用解法 1 求出，而 𝑇1T1 的数量可以通过略微修改解法 2 求出：考虑将两个操作变为「将 𝑇1T1 中每一个元素自增」、「在 𝑇1T1 中加一个值为 ⌊√𝑛⌋ +1⌊n⌋+1 的元素」．容易列出状态转移方程．
将 𝑛n 拆为 𝐴A 和 𝐵B 两部分．枚举其中一个即可得出另一个．将满足 ∑𝑇1 =𝐴∑T1=A 的 𝑇1T1 个数和 ∑𝑇2 =𝐵∑T2=B 的 𝑇2T2 个数求出，乘起来，对所有的 𝐴A 求和便是最终结果．
由于在计算 𝑇1T1 个数的过程中，𝑀 ≤√𝑛M≤n，所以我们利用解法 1 计算 𝑇1T1 的时间复杂度为 Θ(𝑛3/2)Θ(n3/2)．同样地，由于在计算 𝑇2T2 个数的过程中，|𝑇2| ≤∑𝑇2√𝑛 ≤𝑛√𝑛 =√𝑛|T2|≤∑T2n≤nn=n，所以我们利用解法 2 计算 𝑇2T2 的时间复杂度也是 Θ(𝑛3/2)Θ(n3/2)．所以总时间复杂度为 Θ(𝑛3/2)Θ(n3/2)．
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Tiphereth-A, FFjet, Ir1d, OIer1048576 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用