State Design Optimization

Overview

When optimizing dp, one can not only start with the transition process and accelerate transitions. Sometimes one can also start with the state definition and optimize complexity by changing how the state is designed.

What is rather troublesome is that most of these optimizations are not general-purpose; that is, they cannot be applied to multiple problems in a routine way. Therefore, the following sections start from concrete example problems and strive to provide inspiration at the level of ideas, hoping to be of some help to readers.

Example 1

Problem Statement

Given two strings of lengths $n,m$ respectively, consisting only of lowercase letters, $A,B$, find the longest common subsequence of $A,B$. $(n\le 10^6,m\le 10^3)$

Naive Solution

You solved it instantly at a glance—isn't this a standard problem?

Define the state $f_{i,j}$ as the longest common subsequence of $A$'s first $i$ characters and $B$'s first $j$ characters. Then:

$$f_{i,j}= \begin{cases} \max(f_{i-1,j},f_{i,j-1}) & ,A_i \neq B_j \\ f_{i-1,j-1}+1 & ,A_i = B_j \end{cases}$$

The time complexity of the above method is $O(nm)$, so it cannot pass this problem.

Better Solution

Thinking carefully, we find a property: the final answer will not exceed $m$.

Thinking carefully again, we find that LCS has a greedy property.

Redefine $f_{i,j}$ as the shortest prefix length of $A$ whose longest common subsequence with the first $i$ characters of $B$ has length $j$ (that is, exchange the answer and the first-dimensional state of the naive method).

By preprocessing, for every position of $A$, the positions of the next occurrences of $a,b,\cdots,z$, a forward transition can be performed in $O(1)$.

The complexity is $O(m^2+26n)$, so this solution can pass the problem.

Example 2

Problem Statement

Given an unweighted directed graph with $n$ vertices, determine whether it contains a Hamiltonian cycle. $(2\le n\le 20)$

Naive Solution

Looking at the data range, we consider state compression.

Let $f_{s,i}$ indicate whether vertex $i$ can be reached from vertex $1$ by visiting only vertices in the set $s$. Let $g$ be the adjacency matrix of the original graph. Then:

$$f_{s, i} = \bigvee_{j\in s, j\neq i}f_{s \setminus \{i\}, j}\wedge g_{j, i} \left(i\in s\right)$$

The time complexity is $O(n^2 \times 2^n)$. It may pass if written attractively, but it is not elegant.

Better Solution

In the state design above, each $dp$ value represents only one bool value, which seems wasteful.

For each state $s$, we can consider compressing $f_{s,1},f_{s,2},\dots,f_{s,n}$ into one int. We find that after compressing the adjacency matrix in the same way, transitions can be performed in $O(1)$.

The time complexity is $O(n^2/w\times 2^n)$, which can pass this problem, where $w$ is the number of bits in an int.

Example 3

Problem Statement

The standard knapsack problem. $n$ is the number of items, $m$ is the knapsack capacity, and $v_i, w_i$ are the volume and value of item $i$, respectively. $1 \le n \le 10^3$, $1 \le m, v_i \le \color{red}{10^{18}}$, $1 \le \sum w_i \le 10^3$.

Naive Solution

This is a standard knapsack problem.

Define $f_{i, j}$ as the maximum total value when the first $i$ items have been selected and the knapsack currently contains capacity $j$.

It is easy to obtain $f_{i, j} = \max(f_{i - 1, j}, f_{i - 1, j - v_i} + w_i)$.

$v_i \le 10^{18}$, so this problem cannot be passed.

Better Solution

Swap the answer and the second dimension of the state. Let $f_{i, j}$ be the minimum total volume when the first $i$ items have been selected and the value of the items in the knapsack is $j$.

Again, it is easy to obtain $f_{i, j} = \min(f_{i - 1, j}, f_{i - 1, j - w_i} + v_i)$.

Note that after changing the second dimension of the state, the transition must be changed accordingly as well.

The time complexity is $O(n \sum w_i)$, so this solution can pass the problem.