状态设计优化

概述

优化 dp 时，不止可以从转移过程入手，加速转移。有时，也可以从状态定义入手，通过改变设计状态的方式实现复杂度上的优化。

令人比较头疼的是，这类优化大多不具有通用性，即不能很套路地应用于多个题目中。因此，下文将从具体例题出发，力求提供思路上的启发，希望可以对读者有一定帮助。

例 1

题面

给定两个长度分别为 n,m 且仅由小写字母构成的字符串 A,B , 求 A,B 的最长公共子序列。 (n\le 10^6,m\le 10^3)

朴素的解法

您一眼秒了它，这不是板子吗？

定义状态 f_{i,j} 为 A 的前 i 位与 B 的前 j 位最长公共子序列，则有

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}

上述做法的时间复杂度 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 为原图的邻接矩阵。则有

f_{s, i} = \bigcap_{j\in s, j\neq i}f_{s - \left\{i\right\}, j}\cap g_{j, i} \left(i\in s\right)

时间复杂度 O(n^2 \times 2^n) ，写得好看或许能过，但是并不优美。

更优的解法

上面的状态设计中，每个 dp 值只代表一个 bool 值，这让我们觉得有些浪费。

我们可以考虑对于每个状态 s 将 f_{s,1},f_{s,2},\dots,f_{s,n} 压成一个 int，发现我们可以将邻接矩阵同样压缩后进行 O(1) 转移。

时间复杂度 O(n\times 2^n) , 可以通过这道题。

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：Marcythm, partychicken, Xeonacid
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论