State Design Optimization
Overview
When optimizing dynamic programming, we can not only focus on accelerating the transition process. Sometimes, we can also start from the state definition itself, achieving complexity optimization by redesigning the states.
A more troublesome aspect is that most of these optimizations are not universal, meaning they cannot be routinely applied to multiple problems. Therefore, the following sections will start from specific examples, striving to provide inspiration in terms of ideas, hoping to offer some help to readers.
Example 1
Problem Statement
Given two strings \(A\) and \(B\) of lengths \(n\) and \(m\) respectively, consisting only of lowercase letters, find the longest common subsequence of \(A\) and \(B\). \((n\le 10^6,m\le 10^3)\)
Naive Solution
You instantly recognize it—isn't this a standard problem?
Define state \(f_{i,j}\) as the length of the longest common subsequence of the first \(i\) characters of \(A\) and the first \(j\) characters of \(B\). Then we have
The time complexity of the above approach is \(O(nm)\), which cannot pass this problem.
Better Solution
Upon careful thought, we discover a property: the final answer will not exceed \(m\).
Thinking further, we realize that LCS satisfies a greedy property.
Change the state definition: let \(f_{i,j}\) be the shortest prefix length of \(A\) such that its longest common subsequence with the first \(i\) characters of \(B\) has length \(j\) (i.e., swap the answer with the first dimension of the state compared to the naive approach).
By preprocessing the next occurrence position of each letter \(a,b,\cdots,z\) for every position in \(A\), we can perform \(O(1)\) forward transitions.
Complexity \(O(m^2+26n)\), which can pass this 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
Considering the data range, we think of bitmask DP.
Let \(f_{s,i}\) denote whether starting from vertex \(1\) and traversing only vertices in set \(s\), we can reach vertex \(i\). Let \(g\) be the adjacency matrix of the original graph. Then we have
Time complexity \(O(n^2 \times 2^n)\). With careful implementation, it might pass, but it is not elegant.
Better Solution
In the above state design, each \(dp\) value only represents a bool value, which feels somewhat wasteful.
We can consider compressing \(f_{s,1},f_{s,2},\dots,f_{s,n}\) for each state \(s\) into a single int. We find that we can also compress the adjacency matrix and perform \(O(1)\) transitions.
Time complexity \(O(n^2/w\times 2^n)\), which can pass this problem, where \(w\) is the bit-width of int.
Example 3
Problem Statement
A classic knapsack problem. \(n\) is the number of items, \(m\) is the knapsack capacity, \(v_i, w_i\) are the volume and value of the \(i\)-th item, \(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 template knapsack problem.
Define state \(f_{i, j}\) as the maximum total value achievable by selecting from the first \(i\) items, with total volume exactly \(j\) in the knapsack.
We easily get \(f_{i, j} = \max(f_{i - 1, j}, f_{i - 1, j - v_i} + w_i)\).
Since \(v_i \le 10^{18}\), this cannot pass the problem.
Better Solution
Swap the answer and the second dimension of the state. Define \(f_{i, j}\) as the minimum total volume achievable by selecting from the first \(i\) items, with total value exactly \(j\).
Similarly, we get \(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 transitions must also be adjusted accordingly.
Time complexity \(O(n \sum w_i)\), which can pass this problem.
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用