跳转至

状态设计优化

概述

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

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

例 1

题面

给定两个长度分别为 且仅由小写字母构成的字符串 , 求 的最长公共子序列。

朴素的解法

您一眼秒了它,这不是板子吗?

定义状态 的前 位与 的前 位最长公共子序列,则有

上述做法的时间复杂度 ,无法通过本题。

更优的解法

我们仔细一想,发现了一个性质:最终答案不会超过

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

更改状态定义 为与 位的最长公共子序列长度为 的最短前缀长度(即将朴素做法的答案与第一维状态对调)

可以通过预处理 的每一位的下一个 的出现位置进行 的顺推转移。

复杂度 ,可以通过本题。

例 2

题面

给定一个 个点的无权有向图,判断该图是否存在哈密顿回路。

朴素的解法

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

表示从点 出发,仅经过点集 中的点能否到达点 。记 为原图的邻接矩阵。则有

时间复杂度 ,写得好看或许能过,但是并不优美。

更优的解法

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

我们可以考虑对于每个状态 压成一个 int,发现我们可以将邻接矩阵同样压缩后进行 转移。

时间复杂度 , 可以通过这道题,其中 int 的位数。

例 3

题面

常规的背包问题。 为物品数量, 为背包容量, 为第 个物品的体积、价值,

朴素的解法

这是一个模板背包题。

定义状态 为选了前 个物品,目前背包里塞了 的容量的最大价值和。

易得

,无法通过此题。

更优的解法

交换答案和状态的第二维,设 为选了前 个物品,目前背包里的物品 的价值为 的最小体积和。

依然,易得

注意状态的第二维改变之后转移也要一起改变。

时间复杂度 ,可以通过此题。