計數 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})\)。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用