Tối ưu hóa thiết kế trạng thái
概述
优化 dp 时，不止可以从转移过程入手，加速转移．有时，也可以从状态定义入手，通过改变设计状态的方式实现复杂度上的优化．
令人比较头疼的是，这类优化大多不具有通用性，即不能很套路地应用于多个题目中．因此，下文将从具体例题出发，力求提供思路上的启发，希望可以对读者有一定帮助．
例 1
题面
给定两个长度分别为 \(n,m\) 且仅由小写字母构成的字符串 \(A,B\), 求 \(A,B\) 的最长公共子序列．\((n\le 10^6,m\le 10^3)\)
朴素的解法
您一眼秒了它，这不是板子吗？
定义状态 \(f_{i,j}\) 为 \(A\) 的前 \(i\) 位与 \(B\) 的前 \(j\) 位最长公共子序列，则有
上述做法的时间复杂度 \(O(nm)\)，无法通过本题．
更优的解法
我们仔细一想，发现了一个性质：最终答案不会超过 \(m\)．
我们又仔细一想，发现 LCS 满足贪心的性质．
更改状态定义 \(f_{i,j}\) 为与 \(B\) 前 \(i\) 位的最长公共子序列长度为 \(j\) 的 \(A\) 的最短前缀长度（即将朴素做法的答案与第一维状态对调）
可以通过预处理 \(A\) 的每一位的下一个 \(a,b,\cdots,z\) 的出现位置进行 \(O(1)\) 的顺推转移．
复杂度 \(O(m^2+26n)\)，可以通过本题．
例 2
题面
给定一个 \(n\) 个点的无权有向图，判断该图是否存在哈密顿回路．\((2\le n\le 20)\)
朴素的解法
看到数据范围，我们考虑状压．
设 \(f_{s,i}\) 表示从点 \(1\) 出发，仅经过点集 \(s\) 中的点能否到达点 \(i\)．记 \(g\) 为原图的邻接矩阵．则有
时间复杂度 \(O(n^2 \times 2^n)\)，写得好看或许能过，但是并不优美．
更优的解法
上面的状态设计中，每个 \(dp\) 值只代表一个 bool 值，这让我们觉得有些浪费．
我们可以考虑对于每个状态 \(s\) 将 \(f_{s,1},f_{s,2},\dots,f_{s,n}\) 压成一个 int，发现我们可以将邻接矩阵同样压缩后进行 \(O(1)\) 转移．
时间复杂度 \(O(n^2/w\times 2^n)\), 可以通过这道题，其中 \(w\) 为 int 的位数．
例 3
题面
常规的背包问题．\(n\) 为物品数量，\(m\) 为背包容量，\(v_i, w_i\) 为第 \(i\) 个物品的体积、价值，\(1 \le n \le 10^3\)，\(1 \le m, v_i \le \color{red}{10^{18}}\)，\(1 \le \sum w_i \le 10^3\)．
朴素的解法
这是一个模板背包题．
定义状态 \(f_{i, j}\) 为选了前 \(i\) 个物品，目前背包里塞了 \(j\) 的容量的最大价值和．
易得 \(f_{i, j} = \max(f_{i - 1, j}, f_{i - 1, j - v_i} + w_i)\)．
\(v_i \le 10^{18}\)，无法通过此题．
更优的解法
交换答案和状态的第二维，设 \(f_{i, j}\) 为选了前 \(i\) 个物品，目前背包里的物品 的价值为 \(j\) 的最小体积和．
依然，易得 \(f_{i, j} = \min(f_{i - 1, j}, f_{i - 1, j - w_i} + v_i)\)．
注意状态的第二维改变之后转移也要一起改变．
时间复杂度 \(O(n \sum w_i)\)，可以通过此题．
Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:Marcythm, partychicken, Xeonacid, hhc0001
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply