状态设计优化

概述

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

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

例 1

题面

给定两个长度分别为 $n, m$ 且仅由小写字母构成的字符串 $A, B$ , 求 $A, B$ 的最长公共子序列。 $(n \leq 10^{6}, m \leq 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 (n m)$ ，无法通过本题。

更优的解法

我们仔细一想，发现了一个性质：最终答案不会超过 $m$ 。

我们又仔细一想，发现 LCS 满足贪心的性质。

更改状态定义 $f_{i, j}$ 为与 $B$ 前 $i$ 位的最长公共子序列长度为 $j$ 的 $A$ 的最短前缀长度（即将朴素做法的答案与第一维状态对调）

可以通过预处理 $A$ 的每一位的下一个 $a, b, \dots, z$ 的出现位置进行 $O (1)$ 的顺推转移。

复杂度 $O (m^{2} + 26 n)$ ，可以通过本题。

例 2

题面

给定一个 $n$ 个点的无权有向图，判断该图是否存在哈密顿回路。 $(2 \leq n \leq 20)$

朴素的解法

看到数据范围，我们考虑状压。

设 $f_{s, i}$ 表示从点 $1$ 出发，仅经过点集 $s$ 中的点能否到达点 $i$ 。记 $g$ 为原图的邻接矩阵。则有

f_{s, i} = \underset{j \in s, j \neq i}{⋁} f_{s ∖ {i}, j} \land g_{j, i} (i \in s)

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

更优的解法

上面的状态设计中，每个 $d p$ 值只代表一个 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 \leq n \leq 10^{3}$ ， $1 \leq m, v_{i} \leq 10^{18}$ ， $1 \leq \sum w_{i} \leq 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} \leq 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})$ ，可以通过此题。

本页面最近更新：2025/6/3 22:49:11，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：hhc0001, Marcythm, partychicken, StudyingFather, Xeonacid, Enter-tainer, hqztrue, Mascros, Mout-sea, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用