状态设计优化
概述
优化 dp 时，不止可以从转移过程入手，加速转移．有时，也可以从状态定义入手，通过改变设计状态的方式实现复杂度上的优化．
令人比较头疼的是，这类优化大多不具有通用性，即不能很套路地应用于多个题目中．因此，下文将从具体例题出发，力求提供思路上的启发，希望可以对读者有一定帮助．
例 1
题面
给定两个长度分别为 𝑛,𝑚n,m
且仅由小写字母构成的字符串 𝐴,𝐵A,B, 求 𝐴,𝐵A,B 的最长公共子序列．(𝑛 ≤106,𝑚 ≤103)(n≤106,m≤103)
朴素的解法
您一眼秒了它，这不是板子吗？
定义状态 𝑓𝑖,𝑗fi,j 为 𝐴A 的前 𝑖i 位与 𝐵B 的前 𝑗j 位最长公共子序列，则有
𝑓𝑖,𝑗={max(𝑓𝑖−1,𝑗,𝑓𝑖,𝑗−1),𝐴𝑖≠𝐵𝑗𝑓𝑖−1,𝑗−1+1,𝐴𝑖=𝐵𝑗fi,j={max(fi−1,j,fi,j−1),Ai≠Bjfi−1,j−1+1,Ai=Bj
上述做法的时间复杂度 𝑂(𝑛𝑚)O(nm)，无法通过本题．
更优的解法
我们仔细一想，发现了一个性质：最终答案不会超过 𝑚m．
我们又仔细一想，发现 LCS 满足贪心的性质．
更改状态定义 𝑓𝑖,𝑗fi,j 为与 𝐵B 前 𝑖i 位的最长公共子序列长度为 𝑗j 的 𝐴A 的最短前缀长度（即将朴素做法的答案与第一维状态对调）
可以通过预处理 𝐴A 的每一位的下一个 𝑎,𝑏,⋯,𝑧a,b,⋯,z 的出现位置进行 𝑂(1)O(1) 的顺推转移．
复杂度 𝑂(𝑚2 +26𝑛)O(m2+26n)，可以通过本题．
例 2
题面
给定一个 𝑛n 个点的无权有向图，判断该图是否存在哈密顿回路．(2 ≤𝑛 ≤20)(2≤n≤20)
朴素的解法
看到数据范围，我们考虑状压．
设 𝑓𝑠,𝑖fs,i 表示从点 11 出发，仅经过点集 𝑠s 中的点能否到达点 𝑖i．记 𝑔g 为原图的邻接矩阵．则有
𝑓𝑠,𝑖=⋁𝑗∈𝑠,𝑗≠𝑖𝑓𝑠∖{𝑖},𝑗∧𝑔𝑗,𝑖(𝑖∈𝑠)fs,i=⋁j∈s,j≠ifs∖{i},j∧gj,i(i∈s)
时间复杂度 𝑂(𝑛2 ×2𝑛)O(n2×2n)，写得好看或许能过，但是并不优美．
更优的解法
上面的状态设计中，每个 𝑑𝑝dp 值只代表一个 bool 值，这让我们觉得有些浪费．
我们可以考虑对于每个状态 𝑠s 将 𝑓𝑠,1,𝑓𝑠,2,…,𝑓𝑠,𝑛fs,1,fs,2,…,fs,n 压成一个 int，发现我们可以将邻接矩阵同样压缩后进行 𝑂(1)O(1) 转移．
时间复杂度 𝑂(𝑛2/𝑤 ×2𝑛)O(n2/w×2n), 可以通过这道题，其中 𝑤w 为 int 的位数．
例 3
题面
常规的背包问题．𝑛n 为物品数量，𝑚m 为背包容量，𝑣𝑖,𝑤𝑖vi,wi 为第 𝑖i 个物品的体积、价值，1 ≤𝑛 ≤1031≤n≤103，1 ≤𝑚,𝑣𝑖 ≤10181≤m,vi≤1018，1 ≤∑𝑤𝑖 ≤1031≤∑wi≤103．
朴素的解法
这是一个模板背包题．
定义状态 𝑓𝑖,𝑗fi,j 为选了前 𝑖i 个物品，目前背包里塞了 𝑗j 的容量的最大价值和．
易得 𝑓𝑖,𝑗 =max(𝑓𝑖−1,𝑗,𝑓𝑖−1,𝑗−𝑣𝑖 +𝑤𝑖)fi,j=max(fi−1,j,fi−1,j−vi+wi)．
𝑣𝑖 ≤1018vi≤1018，无法通过此题．
更优的解法
交换答案和状态的第二维，设 𝑓𝑖,𝑗fi,j 为选了前 𝑖i 个物品，目前背包里的物品 的价值为 𝑗j 的最小体积和．
依然，易得 𝑓𝑖,𝑗 =min(𝑓𝑖−1,𝑗,𝑓𝑖−1,𝑗−𝑤𝑖 +𝑣𝑖)fi,j=min(fi−1,j,fi−1,j−wi+vi)．
注意状态的第二维改变之后转移也要一起改变．
时间复杂度 𝑂(𝑛∑𝑤𝑖)O(n∑wi)，可以通过此题．
本页面最近更新： 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 协议之条款下提供，附加条款亦可能应用