Counting DP

Counting DP is a method that uses a memorized search similar to DP (which differs somewhat from DP in the narrow sense, namely optimization problems) to solve counting (and summation) problems.

Basics

Basic idea

A counting problem generally asks for the size of a set $S$. In OI, the size of $S$ may sometimes reach the order of $\Theta(n^n)$ or even $\Theta(2^{n!})$ (of course, it is generally taken modulo some fixed number), where $n$ is the problem size, so we cannot find the elements of $S$ one by one.

If we can divide $S$ into several pairwise disjoint subsets, then the number of elements in $S$ equals the sum of the numbers of elements in these parts. If counting these subsets happens to resemble the original problem, we can solve it using a method similar to dynamic programming.

Example

Example

Given a positive integer $n$, find the number of ways to express $n$ as the sum of $k$ positive integers, where changing the positions counts as a different partition.

Let $S_{n,k}$ be the set of tuples of positive integers of the form $(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, the range of $a_k$ is $[1, n - k + 1] \cap \mathbb Z$. Therefore, $S_{n,k}$ can be partitioned according to $a_k$ into $n - k + 1$ subsets. When $a_k = i$, the subset is:

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

The number of elements in this subset is clearly equal to that of $S_{n-i,k-1}$, and because the values of $i$ differ, these subsets are pairwise disjoint. Therefore:

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

We can therefore process this using a method similar to DP: let $f_{n,k}$ be $|S_{n,k}|$. Then the state transition is:

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

Thus, it can be solved using DP.

Similarities to and differences from optimization DP

We can see that both counting DP and optimization DP find a value (a size or an optimum) over a domain $\Omega$. This value is obtained by processing every element in $\Omega$ once and then aggregating the processed values once.

For example, in the 0-1 knapsack problem, the elements of $\Omega$ are the sets of all items in the knapsack. For a solution in $\Omega$, $S$, we process $S$ once; the result $w(S)$ is the total value of the items in $S$. We take the maximum over all processed values to obtain the answer.

For a counting problem, the elements of $\Omega$ are the set $S$ whose number of elements is to be computed. Its processing changes every element of $S$ to $1$, and then aggregates these $1$s by addition. Since every element of $S$ corresponds to one $1$, the resulting value is the number of elements in $S$.

When the aggregation operation is taking a maximum or minimum, we may divide $\Omega$ into any number of parts, as long as their union is $\Omega$; pairwise disjointness is not required. Counting problems do not satisfy this condition, so we need to divide $\Omega$ into parts that are pairwise disjoint. This is the difference from optimization DP.

Example

Example

Given a positive integer $n$, find the number of ways to express $n$ as the sum of any number of positive integers, where changing the positions counts as the same partition.

Solution 1

The elements of the set to be computed are positive-integer multisets whose sum is $n$. However, this is clearly not easy to derive from directly.

If a multiset $T$ contains only positive integers $\le M$ and the sum of all elements in $T$ is $n$, define $T \in S_{n, M}$. Consider the number of occurrences of $M$. It may be $k \in \left[0, \left\lfloor \dfrac nM \right\rfloor\right] \cap \mathbb Z$. Thus, it can transition to $S_{n - kM, M - 1}$. Summing over these gives a complexity of $\Theta(n^2 \log n)$ (the $\log$ comes from the harmonic series caused by the range of $k$).

However, this is still not good 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}$$

Substitution gives $f_{11, 3} = f_{11, 2} + f_{8, 3}$, $f_{12, 3} = f_{12, 2} + f_{9, 3}$, and $f_{13, 3} = f_{13, 2} + f_{10, 3}$. Similarly, we can obtain a general state transition:

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

The time complexity is now $\Theta(n^2)$.

Solution 2

Considering that a multiset of positive integers $T$ can necessarily be obtained by the two operations “increment every element in $T$” and “add to $T$ an element with value $1$”, different operation sequences produce different results.

Thus, the transition for $T$ can be changed into a transition for operation sequences. Consider the last operation in an operation sequence that partitions $n$ into $m$ numbers (denote all such operation sequences by $B_{n,m}$). If it is operation $1$, the number of elements does not increase, but $\sum T$ increases by $m$. For the final $\sum T = n$, the sum of the original $T$ (denoted by $T'$) must be $n-m$. Hence $B_{n,m} \to B_{n-m,m}$. If it is operation $2$, the number of elements increases by one and $\sum T$ increases by $1$. Hence $B_{n,m} \to B_{n-1,m-1}$.

The time complexity remains $\Theta(n^2)$.

Solution 3

Consider dividing $T$ into the part greater than $\sqrt n$, $T_1$, and the part less than or equal to $\sqrt n$, $T_2$. $T_2$ can be found using Solution 1, while the number of $T_1$ can be found by slightly modifying Solution 2: change the two operations to “increment every element in $T_1$” and “add to $T_1$ an element with value $\lfloor \sqrt n \rfloor + 1$”. The state transition can be written down easily.

Split $n$ into two parts, $A$ and $B$. Enumerating one determines the other. Find the number satisfying $\sum T_1 = A$ among $T_1$ and the number satisfying $\sum T_2 = B$ among $T_2$, multiply them, and sum over all $A$ to obtain the final result.

When computing the number of $T_1$, we have $M \le \sqrt n$, so using Solution 1 to compute $T_1$ takes $\Theta(n^{3/2})$ time. Similarly, when computing the number of $T_2$, $|T_2| \le \dfrac{\sum T_2}{\sqrt n} \le \dfrac{n}{\sqrt n} = \sqrt n$, so using Solution 2 to compute $T_2$ also takes $\Theta(n^{3/2})$ time. Therefore, the total time complexity is $\Theta(n^{3/2})$.