AIOJ

Introduction

This article introduces the idea of DP on DP and demonstrates how it applies to concrete problems through two examples.

Idea

The term “DP on DP” refers to abstracting the process of solving a subproblem (usually another DP) as an automaton (DFA) during dynamic programming, and then designing a new layer of DP on top of that automaton.

This technique is mainly used for sequence counting, probability, and expectation problems. A typical problem has the following structure:

Given an alphabet $\Sigma$ and a set of “valid sequences” of length $n$ , denoted by $A\subseteq\Sigma^n$ , over it. Depending on the alphabet, the sequences may be binary strings, digit strings, state sequences, and so on.
For each particular sequence $s\in\Sigma^n$ , dynamic programming can determine whether it is valid (that is, $s\in A$ ), calculate its weight, or find a related value.
Finally, we want to count all sequences in $A$ , their total weight, their expected value, and so on.

At this point, enumerating all sequences is infeasible. We therefore abstract the process of “determining whether a sequence is valid” (the inner DP) as a deterministic finite automaton (DFA). In general, for a fixed sequence $s\in\Sigma^n$ , the state function of the inner DP can be written as $g(i,x;s)$ : the value of some quantity after processing the prefix of $s$ of length $i$ , with the other state components equal to $x$ . The corresponding state transition equation of the inner DP is

g(i,\cdot;s) = G(g(i-1,\cdot;s),s_i).

In other words, the function $g(i,\cdot;s)$ is uniquely determined by the previous function $g(i-1,\cdot;s)$ and the current character $s_i$ . If we regard the function $g(i,\cdot;s)$ as a state of an automaton, the state transition equation of the inner DP gives a transition of that automaton. Thus, the automaton $(Q,\Sigma,\delta,q_0,F)$ corresponding to the inner DP has the following structure:

The state set $Q$ consists of every possible $s\in\Sigma^n$ and $i=0,1,\cdots,n$ , together with their corresponding functions $g(i,\cdot;s)$ .
The transition function $\delta:Q\times\Sigma\to Q$ is $G$ in the state transition equation of the inner DP.
The initial state $q_0$ is usually obvious: it is the initial state of the inner DP.
The accepting state set $F$ corresponds to all valid sequences $s\in A$ .

The function $g(i,\cdot;s)$ itself may be quite complex. Therefore, when solving a concrete problem, it is usually necessary to compress the state space using state compression or DFA minimization. This is also the main reason why DP on DP can significantly reduce the time and space complexity compared with brute-force DP.

After abstracting the inner DP as a DFA, we can design a new DP on this DFA to solve the original problem; this is the outer DP. For ease of exposition, consider a simple counting problem. Define the state function of the outer DP as $f(i,q)$ , the number of prefixes of length $i$ that reach state $q\in Q$ in the DFA. Its state transition equation is

f(i,q) = \sum_{c\in\Sigma}\sum_{q'\in Q:\delta(q',c)=q} f(i-1,q').

The initial state is of course $f(0,q_0)$ , and the final answer can usually be obtained by a simple calculation from $\{f(n,q):q\in F\}$ . The outer DP is actually a special case of DP on a DAG.

Examples

The following two examples explain the general approach of DP on DP in detail.

Example 1

Hero meet devil

Given a string over the alphabet ACGT, denoted by $S$ , with $|S|\le 15$ . For every $0\leq i \leq |S|$ , determine how many strings of length $m$ over the alphabet ACGT, denoted by $T$ , have a longest common subsequence with $S$ of length $i$ .

Solution

The first DP that comes to mind is to let $f_{i,j}$ be the number of length- $i$ strings $T$ whose longest common subsequence with $S$ has length $j$ . However, this state cannot be transitioned: the main problem is that we do not know which characters constitute this longest common subsequence.

Consider the naive process for finding the longest common subsequence. Let $g_{i,j}$ be the length of the LCS of $T$ 's first $i$ characters and $S$ 's first $j$ characters. Then

g_{i,j} = \max\{g_{i-1,j},g_{i,j-1},g_{i-1,j-1}+[T_i=S_j]\}.

For a fixed $i$ , recording each value of $g_i$ is enough to maintain the current state of $S$ and the first characters of $T$ —specifically, the first $i$ characters. Since $S$ has length only $15$ , this idea is feasible.

We therefore redefine the state $f_{i,x}$ as the number of length- $i$ strings $T$ whose DP array with $S$ (namely $g_i$ ) is in state $x$ . This DP seems to have many states, but $g_{i,j}-g_{i,j-1}\in\{0,1\}$ , so we can maintain the difference array of $g_i$ ; the number of states is $2^{|S|}$ .

Now consider how to transition. If we know the array $g_i$ and also know $T_{i+1}$ , we can use the naive LCS transition (the DP equation above) to obtain $g_{i+1}$ . Thus, the naive LCS becomes the inner DP that helps transition $f$ .

We enumerate $T_{i+1}$ , take a state $x$ and calculate its transitioned state $x'$ , then update $f_{i+1,x'}$ with $f_{i,x}$ to complete the outer-DP transition. Finally, let $\textit{ans}_i$ be the answer for LCS length $i$ . For each state $S$ , increase $\textit{ans}_{\operatorname{popcount}(S)}$ by $f_{m,S}$ .

Reference Code

#include <cstring>
#include <iostream>
#include <string>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 100;

int T, a[MAXN + 1], h[MAXN + 1];
int g[MAXN + 1], m, n;
int nxt[1 << 16]
       [4];  // State transition table: nx[mask][ch] is the new state after appending ch to state mask
int f[1001]
     [1 << 16];  // DP array: f[i][mask] is the number of ways of length i in state mask
int ans[MAXN +
        1];  // Final answer: ans[i] is the number of length-m strings with i matching positions

void add(int &x, int y) { x = (x + y) % MOD; }

int calc(int mask, int x) {  // Given the current mask state and character
                             // x (0~3), return the new state
  int res = 0;
  for (int i = 0; i < n; ++i) g[i + 1] = g[i] + ((mask >> i) & 1);

  for (int i = 1; i <= n; ++i) {
    if (a[i] == x)
      h[i] = g[i - 1] + 1;
    else
      h[i] = max(h[i - 1], g[i]);
  }

  for (int i = 1; i <= n; ++i)
    if (h[i] > h[i - 1]) res |= (1 << (i - 1));

  return res;
}

int popcount(int x) {  // Count the number of 1s in mask (that is, the number of matched positions)
  int res = 0;
  while (x) {
    res += x & 1;
    x >>= 1;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> T;
  while (T--) {
    string S;
    cin >> S >> m;
    n = S.length();

    memset(f, 0, sizeof(f));
    memset(ans, 0, sizeof(ans));
    memset(a, 0, sizeof(a));

    for (int i = 0; i < n; ++i) {
      if (S[i] == 'A') a[i + 1] = 0;
      if (S[i] == 'C') a[i + 1] = 1;
      if (S[i] == 'G') a[i + 1] = 2;
      if (S[i] == 'T') a[i + 1] = 3;
    }

    int lim = (1 << n);
    for (int i = 0; i < lim; ++i)
      for (int j = 0; j < 4; ++j) nxt[i][j] = calc(i, j);

    f[0][0] = 1;
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < lim; ++j)
        if (f[i][j])
          for (int k = 0; k < 4; ++k) add(f[i + 1][nxt[j][k]], f[i][j]);

    for (int i = 0; i < lim; ++i) add(ans[popcount(i)], f[m][i]);

    for (int i = 0; i <= n; ++i) cout << ans[i] << '\n';
  }

  return 0;
}

Example 2

[ZJOI2019] Mahjong

Suppose there are $n$ tile ranks in Mahjong, with $4$ tiles of each rank. A meld is either three consecutive tiles of ranks $i,i+1,i+2$ (a sequence) or three tiles of the same rank $i,i,i$ (a triplet), and a pair is two tiles of the same rank $i,i$ . A Mahjong hand is winning if and only if, viewed as a multiset, it can be divided into four melds and one pair, or into seven distinct pairs. Given $13$ Mahjong tiles, find the expected number of additional draws needed for the hand to contain a winning subsequence.

Solution

First, for a hand, we only need to consider the count of each tile rank, not their order. Thus, every prefix of any tile sequence can be converted into a length- $n$ sequence whose entries are in $0\sim 4$ . Initially, if the count of rank $i$ is $a_i$ , the $i$ -th number $x_i$ in the converted sequence is restricted to an integer in $[a_i,4]$ . Note that the converted sequence does not consider the order of draws, whereas the Mahjong sequence in the problem does.

Let $X$ be the minimum number of draws needed to win. Directly calculating the expectation $\mathbf E[X]$ is difficult, so consider the following transformation. Let $h_i$ be the number of sequences that are not winning after $i$ tiles have been drawn. In the corresponding Mahjong sequence, these $i$ tiles must appear before the remaining $(4n-13-i)$ tiles, but the order among those $i$ tiles and the remaining $(4n-13-i)$ tiles is arbitrary. Therefore, the number of Mahjong sequences in which drawing only the first $i$ tiles does not produce a win is

h_i\cdot i!(4n-13-i)!.

The total number of Mahjong sequences is $(4n-13)!$ , so the probability that drawing the first $i$ tiles does not produce a win is

\mathbf P[X>i] = \dfrac{h_i\cdot i!(4n-13-i)!}{(4n-13)!}.

Using the tail-sum formula, we obtain the desired expectation:

\mathbf E[X] = \sum_{i=0}^\infty\mathbf P[X>i] = 1 + \sum_{i=1}^{4n-13}\dfrac{h_i\cdot i!(4n-13-i)!}{(4n-13)!}.

The problem has now been reduced to computing $h_i$ . We solve it using DP on DP.

First consider the inner DP, which uses dynamic programming to determine whether a converted sequence represents a winning hand. The seven-pairs case is relatively easy, so we focus on the first winning form. Let $g_{0/1,i,j,k}$ denote the maximum number of melds after processing the first $i$ ranks, with $j$ groups of $(i−1,i)$ and $k$ tiles of rank $i$ remaining, and with a pair present/absent (that is, $0/1$ ). If we run the DP on a sequence and the final $g_{1,n}$ contains a number greater than or equal to $4$ , then the sequence is winning.

The state transition of this DP is fairly complicated. We discuss it in two steps. First, consider the transition of $g_{0/1,i}$ . This means that after adding $x_i$ tiles of rank $i$ to the current hand, without forming a new pair, we determine how the number of melds changes. If, after adding $x_i$ tiles of rank $i$ , we want to obtain $\ell$ sequences, $j$ groups of $(i-1,i)$ , and $k$ standalone tiles of rank $i$ , then we should transition from $(g_{0/1,i-1})_{\ell,j}$ (this choice minimizes waste as much as possible), and use the remaining $(x_i-\ell-j-k)$ tiles to form as many triplets as possible. Enumerating all possibilities gives the following transition equation:

\tilde G(g_{0/1,i-1}, x_i)_{j,k} = \max\left\{(g_{0/1,i-1})_{\ell,j} + \ell + \left\lfloor\dfrac{x_i-\ell-j-k}{3}\right\rfloor:\ell+j+k\le x_i\right\}.

Second, consider the case where a pair must be formed. When adding $x_i$ tiles of rank $i$ , there are three transitions:

Transition $g_{0,i-1}$ with $x_i$ added tiles to $g_{0,i}$ .
Transition $g_{1,i-1}$ with $x_i$ added tiles to $g_{1,i}$ .
If $x_i\ge 2$ , transition $g_{0,i-1}$ with $x_i-2$ added tiles to $g_{1,i}$ .

These are all the transitions from $g_{i-1}$ after adding $x_i$ tiles, yielding $g_i$ .

Once the state transitions of the inner DP are solved, we can construct the winning-hand automaton. The automaton transitions are exactly the transitions of the inner DP above; we must also decide how to represent each automaton state. Each state corresponds to one possible value of $g_i$ . Its three dimensions are $(0/1,j,k)$ . The dimensions indexed by $j$ and $k$ retain $(i-1,i)$ groups and $i$ tiles, respectively, for forming sequences later. Since three identical sequences can always be rearranged into three triplets, we only need to consider the need to form at most $2$ identical sequences, so each tile type needs to retain at most $2$ : $j,k\in\{0,1,2\}$ . Thus, $g_i$ can be represented by a $2\times 3\times 3$ array. In addition, to maintain the seven-pairs winning form, each state needs a counter representing the maximum number of pairs that can currently be formed.

Each element of the array $g_i$ may take a value in $\{-\infty\}\cup\mathbf N$ . However, since a meld count of at least $4$ is already winning, every element can be capped at $4$ . Since adding any tile to a winning sequence still yields a winning sequence, DFA minimization lets us compress all winning states into a single state. Therefore, for non-winning states, each position only needs to consider $\{-\infty\}\cup\{0,1,2,3\}$ . In the implementation, $-\infty$ is represented by $-1$ .

Even so, there are still many possible states: $1+7\times 5^{18}$ . It is not realistic to enumerate them all. In fact, most of these possibilities never occur in a winning-hand automaton. To avoid considering states that do not actually exist, use the idea of BFS: start from the initial state and expand states one step at a time, stopping when a winning state is reached. The resulting automaton has $N = 2092$ states.

Finally, consider how to run a DP on the winning-hand automaton (the outer DP). Let $f_{i,j,k}$ be the number of sequences that have processed the first $i$ ranks, have drawn $j$ tiles in total, and have reached state $k$ of the winning-hand automaton. During the transition, enumerate the number of drawn tiles $0\leq t\leq 4-a_i$ , where $a_i$ is the number of the initial $13$ tiles that are of rank $i$ . Multiply the previous sequence count by the number of ways to choose from the $4−a_i$ remaining tiles a total of $t$ tiles, namely $\dbinom{4-a_i}{t}$ , and accumulate. Formally,

f_{i+1,j+t,k'} = \sum_{t=0}^{4-a_i}\dbinom{4-a_i}{t}f_{i,j,k}.

Here, $k'=\delta(k,a_i+t)$ is the state obtained by adding tiles to automaton state $k$ , specifically $a_i+t$ tiles. After the outer DP ends, we can calculate the number of sequences that have drawn $i$ tiles and are still not winning:

h_i=\sum_{j=1}^{N} f_{n,i,j}.

Substituting this into the expression above gives the desired expectation.