优化 dp 时，不止可以从转移过程入手，加速转移。有时，也可以从状态定义入手，通过改变设计状态的方式实现复杂度上的优化。
令人比较头疼的是，这类优化大多不具有通用性，即不能很套路地应用于多个题目中。因此，下文将从具体例题出发，力求提供思路上的启发，希望可以对读者有一定帮助。
[!NOTE] 题面
给定两个长度分别为 $n,m$ 且仅由小写字母构成的字符串 $A,B$, 求 $A,B$ 的最长公共子序列。$(n\le 10^6,m\le 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(nm)$，无法通过本题。
我们仔细一想，发现了一个性质：最终答案不会超过 $m$。
我们又仔细一想，发现 LCS 满足贪心的性质。
更改状态定义 $f_{i,j}$ 为与 $B$ 前 $i$ 位的最长公共子序列长度为 $j$ 的 $A$ 的最短前缀长度（即将朴素做法的答案与第一维状态对调）
可以通过预处理 $A$ 的每一位的下一个 $a,b,\cdots,z$ 的出现位置进行 $O(1)$ 的顺推转移。
复杂度 $O(m^2+26n)$，可以通过本题。
[!NOTE] 题面
给定一个 $n$ 个点的无权有向图，判断该图是否存在哈密顿回路。$(2\le n\le 20)$
看到数据范围，我们考虑状压。
设 $f_{s,i}$ 表示从点 $1$ 出发，仅经过点集 $s$ 中的点能否到达点 $i$。记 $g$ 为原图的邻接矩阵。则有
$$
f_{s, i} = \bigcap_{j\in s, j\neq i}f_{s - \left{i\right}, j}\cap g_{j, i} \left(i\in s\right)
$$
时间复杂度 $O(n^2 \times 2^n)$，写得好看或许能过，但是并不优美。
上面的状态设计中，每个 $dp$ 值只代表一个 bool 值，这让我们觉得有些浪费。
我们可以考虑对于每个状态 $s$ 将 $f_{s,1},f_{s,2},\dots,f_{s,n}$ 压成一个 int，发现我们可以将邻接矩阵同样压缩后进行 $O(1)$ 转移。
时间复杂度 $O(n\times 2^n)$, 可以通过这道题。