Counting DP

Counting DP is a method that utilizes DP-like memoized search (distinct from DP in the narrow sense, which deals with optimization problems) to solve counting (and summation) problems.

Basics

Basic Idea

Counting problems generally involve finding the size of a set \(S\). In OI, the size of \(S\) can sometimes reach levels like \(\Theta(n^n)\) or even \(\Theta(2^{n!})\) (though usually modulo a fixed number), where \(n\) is the problem size, so we cannot enumerate all elements of \(S\).

If we can partition \(S\) into several disjoint subsets, then the number of elements in \(S\) equals the sum of the numbers of elements in these parts. If the counting of these subsets is similar to the original problem, we can solve it using a dynamic programming-like approach.

Example

Given a positive integer \(n\), find the number of ways to partition \(n\) into \(k\) positive integers, considering different orders as distinct partitions.

Let the set \(S_{n,k}\) consist of all \(k\)-tuples of positive integers \((a_1, \dots, a_k)\) such that \(a_1 + \dots + a_k = n\). If \(a_k\) is fixed, we have the following derivation: since \(a_1 + a_2 + \dots + a_{k-1} + a_k = n\), we have \(a_1 + a_2 + \dots + a_{k-1} = n - a_k\). By the definition of \(S_{n,k}\), \((a_1, a_2, \dots, a_{k-1}) \in S_{n - a_k, k - 1}\).

Since \(a_1, a_2, \dots, a_k\) are positive integers, \(a_k\) ranges over \([1, n - k + 1] \cap \mathbb Z\). Therefore, \(S_{n,k}\) can be partitioned according to \(a_k\) into \(n - k + 1\) subsets, where when \(a_k = i\), the subset is:

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

The size of this subset is clearly \(|S_{n-i,k-1}|\). Since \(i\) varies, these subsets are pairwise disjoint. Thus:

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

This allows us to handle it with a DP-like approach: let \(f_{n,k} = |S_{n,k}|\), then we have the state transition equation:

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

Now we can solve it using DP.

Similarities and Differences with Optimization DP

It can be observed that both counting DP and optimization DP involve finding a value (size or optimal value) within a domain \(\Omega\). This value is obtained by processing all elements in \(\Omega\) and then aggregating the processed values.

For example, in the 0-1 knapsack problem, the elements of \(\Omega\) are all subsets of items in the knapsack. For a scheme \(S \in \Omega\), we process it to get \(w(S)\), the total value of items in \(S\). Then we take the maximum over all processed values to get the answer.

For counting problems, the elements of \(\Omega\) are the set \(S\) whose size we want to compute. The processing maps every element of \(S\) to \(1\), and then these \(1\)s are aggregated via addition. Since each element of \(S\) corresponds to a \(1\), the resulting value is the size of \(S\).

When the aggregation operation is max/min, we can partition \(\Omega\) into any number of parts, as long as their union is \(\Omega\); they need not be disjoint. However, for counting problems, this condition is not sufficient. We require the parts to be pairwise disjoint, which is the key difference from optimization DP.

Example

Given a positive integer \(n\), find the number of ways to partition \(n\) into any number of positive integers, considering different orders as identical partitions.

Solution 1

The elements to count are multisets of positive integers whose sum is \(n\). This is not easy to derive directly.

Let \(T\) be a multiset containing only positive integers \(\le M\), with sum \(n\). Denote \(T \in S_{n, M}\). Consider the number of times \(M\) appears, which can be \(k \in \left[0, \left\lfloor \dfrac nM \right\rfloor\right] \cap \mathbb Z\). Then it can be transferred to \(S_{n - kM, M - 1}\). Summing over \(k\) gives the count. The complexity is \(\Theta(n^2 \log n)\) (the \(\log\) factor comes from the harmonic series due to the range of \(k\)).

But this is not efficient enough. Consider the following example:

\[ \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} \]

Substituting equal terms gives \(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}\). Similarly, we can derive a general state transition equation:

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

Now the time complexity is \(\Theta(n^2)\).

Solution 2

Consider that any multiset \(T\) of positive integers can be obtained by repeatedly applying two operations: "increment every element in \(T\) by 1" and "add an element with value 1 to \(T\)". Moreover, different sequences of operations yield different results.

Thus, the transition for \(T\) can be transformed into a transition on operation sequences. Consider the last operation in a sequence of operations that partitions \(n\) into \(m\) numbers (all such sequences are denoted \(B_{n,m}\)). If it is operation 1, it does not increase the count of numbers but increases \(\sum T\) by \(m\). To achieve \(\sum T = n\), the original \(T\) (denoted \(T'\)) must have sum \(n-m\). So \(B_{n,m} \to B_{n-m,m}\). If it is operation 2, it adds one number and increases \(\sum T\) by 1. So \(B_{n,m} \to B_{n-1,m-1}\).

The time complexity of this approach is also \(\Theta(n^2)\).

Solution 3

Partition \(T\) into two parts: \(T_1\) containing elements greater than \(\sqrt n\), and \(T_2\) containing elements less than or equal to \(\sqrt n\). \(T_2\) can be computed using Solution 1, while the count for \(T_1\) can be obtained by slightly modifying Solution 2: change the two operations to "increment every element in \(T_1\) by 1" and "add an element with value \(\lfloor \sqrt n \rfloor + 1\) to \(T_1\)". The state transition equation can be easily written.

Split \(n\) into two parts \(A\) and \(B\). Enumerating one yields the other. Multiply the number of \(T_1\) with \(\sum T_1 = A\) by the number of \(T_2\) with \(\sum T_2 = B\), and sum over all \(A\) to get the final result.

Since in computing \(T_1\), we have \(M \le \sqrt n\), the time complexity using Solution 1 is \(\Theta(n^{3/2})\). Similarly, for \(T_2\), we have \(|T_2| \le \dfrac{\sum T_2}{\sqrt n} \le \dfrac{n}{\sqrt n} = \sqrt n\), so using Solution 2 for \(T_2\) also takes \(\Theta(n^{3/2})\). Thus the total time complexity is \(\Theta(n^{3/2})\).

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