状态设计优化
概述
优化 dp 时,不止可以从转移过程入手,加速转移。有时,也可以从状态定义入手,通过改变设计状态的方式实现复杂度上的优化。
令人比较头疼的是,这类优化大多不具有通用性,即不能很套路地应用于多个题目中。因此,下文将从具体例题出发,力求提供思路上的启发,希望可以对读者有一定帮助。
例 1
题面
给定两个长度分别为 𝑛,𝑚
且仅由小写字母构成的字符串 𝐴,𝐵
, 求 𝐴,𝐵
的最长公共子序列。(𝑛 ≤106,𝑚 ≤103)
朴素的解法
您一眼秒了它,这不是板子吗?
定义状态 𝑓𝑖,𝑗
为 𝐴
的前 𝑖
位与 𝐵
的前 𝑗
位最长公共子序列,则有
𝑓𝑖,𝑗={max(𝑓𝑖−1,𝑗,𝑓𝑖,𝑗−1),𝐴𝑖≠𝐵𝑗𝑓𝑖−1,𝑗−1+1,𝐴𝑖=𝐵𝑗
上述做法的时间复杂度 𝑂(𝑛𝑚)
,无法通过本题。
更优的解法
我们仔细一想,发现了一个性质:最终答案不会超过 𝑚
。
我们又仔细一想,发现 LCS 满足贪心的性质。
更改状态定义 𝑓𝑖,𝑗
为与 𝐵
前 𝑖
位的最长公共子序列长度为 𝑗
的 𝐴
的最短前缀长度(即将朴素做法的答案与第一维状态对调)
可以通过预处理 𝐴
的每一位的下一个 𝑎,𝑏,⋯,𝑧
的出现位置进行 𝑂(1)
的顺推转移。
复杂度 𝑂(𝑚2 +26𝑛)
,可以通过本题。
例 2
题面
给定一个 𝑛
个点的无权有向图,判断该图是否存在哈密顿回路。(2 ≤𝑛 ≤20)
朴素的解法
看到数据范围,我们考虑状压。
设 𝑓𝑠,𝑖
表示从点 1
出发,仅经过点集 𝑠
中的点能否到达点 𝑖
。记 𝑔
为原图的邻接矩阵。则有
𝑓𝑠,𝑖=⋁𝑗∈𝑠,𝑗≠𝑖𝑓𝑠∖{𝑖},𝑗∧𝑔𝑗,𝑖(𝑖∈𝑠)
时间复杂度 𝑂(𝑛2 ×2𝑛)
,写得好看或许能过,但是并不优美。
更优的解法
上面的状态设计中,每个 𝑑𝑝
值只代表一个 bool
值,这让我们觉得有些浪费。
我们可以考虑对于每个状态 𝑠
将 𝑓𝑠,1,𝑓𝑠,2,…,𝑓𝑠,𝑛
压成一个 int
,发现我们可以将邻接矩阵同样压缩后进行 𝑂(1)
转移。
时间复杂度 𝑂(𝑛2/𝑤 ×2𝑛)
, 可以通过这道题,其中 𝑤
为 int
的位数。
例 3
题面
常规的背包问题。𝑛
为物品数量,𝑚
为背包容量,𝑣𝑖,𝑤𝑖
为第 𝑖
个物品的体积、价值,1 ≤𝑛 ≤103
,1 ≤𝑚,𝑣𝑖 ≤1018
,1 ≤∑𝑤𝑖 ≤103
。
朴素的解法
这是一个模板背包题。
定义状态 𝑓𝑖,𝑗
为选了前 𝑖
个物品,目前背包里塞了 𝑗
的容量的最大价值和。
易得 𝑓𝑖,𝑗 =max(𝑓𝑖−1,𝑗,𝑓𝑖−1,𝑗−𝑣𝑖 +𝑤𝑖)
。
𝑣𝑖 ≤1018
,无法通过此题。
更优的解法
交换答案和状态的第二维,设 𝑓𝑖,𝑗
为选了前 𝑖
个物品,目前背包里的物品 的价值为 𝑗
的最小体积和。
依然,易得 𝑓𝑖,𝑗 =min(𝑓𝑖−1,𝑗,𝑓𝑖−1,𝑗−𝑤𝑖 +𝑣𝑖)
。
注意状态的第二维改变之后转移也要一起改变。
时间复杂度 𝑂(𝑛∑𝑤𝑖)
,可以通过此题。
本页面最近更新:2025/6/3 22:49:11,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Enter-tainer, partychicken, Xeonacid, hhc0001, Marcythm, StudyingFather, hqztrue, Mascros, Mout-sea, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用