跳转至

# 状态设计优化

## 概述

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

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

## 例 1

题面

给定两个长度分别为 𝑛,𝑚 n,m 且仅由小写字母构成的字符串 𝐴,𝐵 A,B, 求 𝐴,𝐵 A,B 的最长公共子序列．(𝑛 ≤1 0 6,𝑚 ≤1 0 3)(n≤10 6,m≤10 3)

### 朴素的解法

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

定义状态 𝑓 𝑖,𝑗 f i,j 为 𝐴 A 的前 𝑖 i 位与 𝐵 B 的前 𝑗 j 位最长公共子序列，则有

𝑓 𝑖,𝑗={m a x(𝑓 𝑖−1,𝑗,𝑓 𝑖,𝑗−1),𝐴 𝑖≠𝐵 𝑗 𝑓 𝑖−1,𝑗−1+1,𝐴 𝑖=𝐵 𝑗 f i,j={max(f i−1,j,f i,j−1),A i≠B j f i−1,j−1+1,A i=B j

上述做法的时间复杂度 𝑂(𝑛 𝑚)O(n m)，无法通过本题．

### 更优的解法

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

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

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

可以通过预处理 𝐴 A 的每一位的下一个 𝑎,𝑏,⋯,𝑧 a,b,⋯,z 的出现位置进行 𝑂(1)O(1) 的顺推转移．

复杂度 𝑂(𝑚 2 +2 6 𝑛)O(m 2+26 n)，可以通过本题．

## 例 2

题面

给定一个 𝑛 n 个点的无权有向图，判断该图是否存在哈密顿回路．(2 ≤𝑛 ≤2 0)(2≤n≤20)

### 朴素的解法

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

设 𝑓 𝑠,𝑖 f s,i 表示从点 1 1 出发，仅经过点集 𝑠 s 中的点能否到达点 𝑖 i．记 𝑔 g 为原图的邻接矩阵．则有

𝑓 𝑠,𝑖=⋁𝑗∈𝑠,𝑗≠𝑖 𝑓 𝑠∖{𝑖},𝑗∧𝑔 𝑗,𝑖(𝑖∈𝑠)f s,i=⋁j∈s,j≠i f s∖{i},j∧g j,i(i∈s)

时间复杂度 𝑂(𝑛 2 ×2 𝑛)O(n 2×2 n)，写得好看或许能过，但是并不优美．

### 更优的解法

上面的状态设计中，每个 𝑑 𝑝 d p 值只代表一个 `bool` 值，这让我们觉得有些浪费．

我们可以考虑对于每个状态 𝑠 s 将 𝑓 𝑠,1,𝑓 𝑠,2,…,𝑓 𝑠,𝑛 f s,1,f s,2,…,f s,n 压成一个 `int`，发现我们可以将邻接矩阵同样压缩后进行 𝑂(1)O(1) 转移．

时间复杂度 𝑂(𝑛 2/𝑤 ×2 𝑛)O(n 2/w×2 n), 可以通过这道题，其中 𝑤 w 为 `int` 的位数．

## 例 3

题面

常规的背包问题．𝑛 n 为物品数量，𝑚 m 为背包容量，𝑣 𝑖,𝑤 𝑖 v i,w i 为第 𝑖 i 个物品的体积、价值，1 ≤𝑛 ≤1 0 3 1≤n≤10 3，1 ≤𝑚,𝑣 𝑖 ≤1 0 1 8 1≤m,v i≤10 18，1 ≤∑𝑤 𝑖 ≤1 0 3 1≤∑w i≤10 3．

### 朴素的解法

这是一个模板背包题．

定义状态 𝑓 𝑖,𝑗 f i,j 为选了前 𝑖 i 个物品，目前背包里塞了 𝑗 j 的容量的最大价值和．

易得 𝑓 𝑖,𝑗 =m a x(𝑓 𝑖−1,𝑗,𝑓 𝑖−1,𝑗−𝑣 𝑖 +𝑤 𝑖)f i,j=max(f i−1,j,f i−1,j−v i+w i)．

𝑣 𝑖 ≤1 0 1 8 v i≤10 18，无法通过此题．

### 更优的解法

交换答案和状态的第二维，设 𝑓 𝑖,𝑗 f i,j 为选了前 𝑖 i 个物品，目前背包里的物品 的价值为 𝑗 j 的最小体积和．

依然，易得 𝑓 𝑖,𝑗 =m i n(𝑓 𝑖−1,𝑗,𝑓 𝑖−1,𝑗−𝑤 𝑖 +𝑣 𝑖)f i,j=min(f i−1,j,f i−1,j−w i+v i)．

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

时间复杂度 𝑂(𝑛∑𝑤 𝑖)O(n∑w i)，可以通过此题．

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