一、状态数优化

1. 状态数的自简化

有时候，真正有用的 $dp$ 状态非常少。通过观察状态的实际可达范围，可以主动缩小 $dp$ 数组规模，从而减少求解时间。

例题 1：A96798.美丽数组

题意：给定数组 $a$ ，求所有长度为 $k$ 的子序列 $b$ 的美丽值之和。美丽值定义为：

$\min_{1\le i<j\le k}\lvert b_i-b_j\rvert$

思路：

将 $b$ 排序后，若相邻差的最小值为 $x$ ，则有：

$b_k-b_1 \ge (k-1)x \quad\Rightarrow\quad x \le \frac{b_k-b_1}{k-1}$

因此美丽值的取值范围相对较小。

直接计算“美丽值恰好等于 $x$ ”较困难，改为计算“美丽值 $\geq x$ ”的方案数，再做差分更容易。

固定阈值 $lim$ ，定义：

$dp[i][j] : \text{在前 } i \text{ 个数中，选了 } j \text{ 个，且最后一个选的是 } a_i \text{ 的方案数}$

转移：

$dp[i][j] = \sum_{\substack{k<i\\ a_i-a_k\ge lim}} dp[k][j-1]$

优化：

对每个 $i$ ，满足 $a_i-a_k\ge lim$ 的最大可行 $k$ 随 $i$ 单调变化；
用双指针 + 前缀和维护可转移区间，即可把每次转移从 $O(n)$ 降到 $O(1)$ 。

最终对每个 $lim$ ：

$cnt[lim] = \sum_{i=k}^{n} dp[i][k]$

再对 $cnt[\cdot]$ 做一次差分即可得到“美丽值恰为 $lim$ ”的方案数，并累加贡献。

例题 2：A96797.Hack，还是不 Hack，这是个问题

题意：

有 $3$ 道题，每题按过题人数决定分值（ $500,1000,\dots,3000$ ）。
你可以 hack 某些人：每 hack 一次加 $100$ 分。
每个人某题得分形如：

$score_i=\frac{x_i(250-t_i)}{250}$

求最终排名的最小可能值。

思路要点：

总分最大 $9000$ ，因此 hack 次数最多 $90$ ；
能被 hack 的人数量也至多 $90$ 。
先枚举每道题的分值（等价于确定每题可 hack 人数），复杂度 $O(7^3)$ ；
确定后“hack 越多越好”，你的分数可直接计算；
再用 $dp_{i,j,k}$ 统计每题 hack 次数固定时，你能达到的最小排名，时间复杂度约为：

$O(30^3\cdot 90)$

总体复杂度：

$O(7^3\cdot 30^3\cdot 90)$

例题3：[CSP-J 2025] 多边形

题意：给定 $n$ 个小木棍的长度，求 $3$ 个及以上的小木棍的合集中，组成多边形的方案数。

思路： $dp_{i,j}:前i个小木棍当中，组成总和为j的方案数$ ，其中 $j$ 的取值可以很大，但是真正有用的取值只有 $0 \sim 5000$ ，因此任何超过 $5000$ 的总和全部默认为 $5001$ 。

2. 状态合并

在初步设计 $dp$ 时，往往会设计一些“含义清晰但信息冗余”的状态。进一步分析后，若发现其中一些维度并不会影响后续决策，就可以合并这些状态，从而减少状态数。

例题：([CSP-S 2019] Emiya 家今天的饭)

题意：

给定一个二维矩阵a，定义 $a_{i,j}$ 代表了用第 $i$ 种烹饪方法和第 $j$ 种食材做的菜的种数，现有三条规定：

至少做一道菜
每个烹饪方法最多只能做一道菜
所有食材至多在一半的菜中出现

求做菜的方案数

思路：

首先约束所有的食材的出现次数非常的麻烦，于是考虑正难则反，有且仅有一种主要食材的出现次数会超过一半，考虑求解这一类的方案数即可。

顺着这点继续往下思考，我们可以依次枚举每一种主要食材（列），然后依次求出它们超过一半的方案数。接着我们需要知道当前这一列做了几道菜以及总共做了几道菜，于是就有了状态定义： $f_{i,j,k}$ 代表了前 $i$ 行当中，选择了 $j$ 道菜，其中有 $k$ 道菜是当前食材做的方案数。

令 $s_i=\sum_{j=1}^m a_{i,j}$ ，于是总方案数即为：

$\text{tot}=\prod_{i=1}^n (s_i+1)-1$

容易想到 DP 求不合法的方案数。我们枚举被选择的数量超过了总数量一半的那一列 (c)，然后令 (f_{i,j,k}) 表示考虑前 (i) 行，总共选择了 (j) 个位置，第 (c) 列选择了 (k) 个位置的方案数。转移时考虑当前行不选、选第 (c) 列之外的位置或选择第 (c) 列的位置，即可得到转移方程：

$f_{i,j,k} = f_{i-1,j,k} + f_{i-1,j-1,k}\cdot (s_i-a_{i,c}) + f_{i-1,j-1,k-1}\cdot a_{i,c}$

转移时注意 (j) 和 (k) 从 (0) 开始枚举。最终答案就是

$\text{ans} = \text{tot} - \sum_{j=1}^n \sum_{k=\left\lfloor \frac{j}{2}\right\rfloor +1}^{j} f_{n,j,k}$

这么做的时间复杂度是 $O(mn^3)$ 的，还不足以通过本题，于是需要考虑使用优化。

我们会发现： $f_{i,j,k}$ 的后两维都是在描述相似的东西“选了几个”，而我们在乎的仅仅只是第 $c$ 列有没有超过其他列的总数，至于其他列到底选了多少个我们并不在乎。因此我们考虑将两者合并成同一个意义，也就是第 $c$ 列和其他列“相差了几个”。

我们可以将状态变为 $f_{i,j}$ ，表示前 $i$ 行，当前列的数比其他列的数多了 $j$ 个，则有转移：

$f_{i,j} = f_{i-1,j} + a_{i,c}\cdot f_{i-1,j-1} + (s_i-a_{i,c})\cdot f_{i-1,j+1}$

转移仍然是 $O(1)$ 的，但总复杂度降为 $O(mn^2)$ ，可以通过此题。

3. 下标换元（状态重定义）

本节属于状态设计优化：通过状态重定义触发上文的“自简化”或“状态合并”，从而减少状态数。

3.1 状态换元

有时只需转换状态定义，就能把状态数显著压缩。

例题：A96793.Welcome24ever 和巧克力

题意：

给定数组 $a$ 和正整数 $k$ ，构造数组 $b$ ，满足：

$k \le \prod_{i=1}^{n} b_i$

最大化：

$k\cdot \frac{\prod_{i=1}^{n}\left\lfloor\frac{a_i}{b_i}\right\rfloor}{\prod_{i=1}^{n} a_i}, \qquad n=100,\ a_i\le 10^7$

思路：

朴素状态：

$f_{i,j}=\text{前 } i \text{ 个数，使 } \prod_{x=1}^{i} b_x=j \text{ 的最优值}$

但 $j$ 的范围是巨大的，显然不可行。

换元：

$f_{i,j}=\text{考虑前 } i \text{ 个数后，剩余需求为 } j \text{ 的最优值}$

其中

$j=\left\lceil\frac{k}{\prod_{x=1}^{i} b_x}\right\rceil \quad\Longleftrightarrow\quad \prod_{x=i+1}^{n} b_x\ge j$

转移：

$f_{i,\left\lceil\frac{j}{b_i}\right\rceil} \leftarrow f_{i-1,j}\times \left\lfloor\frac{a_i}{b_i}\right\rfloor\times \frac{1}{a_i}$

处理取整：

$\left\lceil\frac{j}{b_i}\right\rceil = \left\lfloor\frac{j-1}{b_i}\right\rfloor+1$

并利用性质：

$\left\lceil \frac{\left\lceil \frac{j}{x} \right\rceil}{y} \right\rceil = \left\lceil \frac{j}{xy}\right\rceil = \left\lfloor \frac{j-1}{xy} \right\rfloor + 1$

因此对任意转移，第二维始终形如：

$\left\lfloor\frac{k-1}{x}\right\rfloor+1$

而 $\left\lfloor\frac{k-1}{x}\right\rfloor$ 的不同取值个数可用整除分块证明为 $O(\sqrt{k})$ ，从而触发状态数自简化：

$\text{状态数 } = O(n\sqrt{k})$

接下来优化转移：不能枚举所有 $b_i$ 。

对固定状态 $f_{i-1,j}$ ，观察到 $\left\lceil\frac{j}{b_i}\right\rceil$ 的不同取值也很少（整除分块，约 $O(\sqrt{j})$ ）。因此：

对每一种可能的 $\left\lceil\frac{j}{b_i}\right\rceil$ 分组；
在组内只取能使 $\left\lfloor\frac{a_i}{b_i}\right\rfloor$ 最大的 $b_i$ （通常取最大的 $b_i$ ）。

于是单次转移复杂度变为：

$O(\sqrt{j})$

总体复杂度可写为：

$O\!\left( n\times \sum_{t=1}^{\sqrt{k}} \left(\sqrt{t}+\sqrt{\frac{k}{t}}\right) \right) = O(n\cdot k^{0.75})$

3.2 转成补集（容斥）

若题目中出现两个限制条件方向相反（ $\le$ 与 $>$ 同时出现），往往难以直接计数。可以对其中一个方向取补集，配合容斥把问题变成“同向限制”。

例题：([CSP-S 2025] 员工招聘)

题意：

给定长度为 $n$ 的 $01$ 串：

$1$ 的位置可以录取人
$0$ 的位置一定不能录取人

共有 $n$ 个人，第 $x$ 个人忍耐度为 $c_x$ 。为所有人分配应聘顺序：若某人在应聘时，前方录取失败人数超过 $c_x$ ，则他一定不会被录取。

求所有方案中，录取人数超过 $m$ 的方案数。

思路：

预处理：只考虑 $1$ 位置

$0$ 位置对“能否录取”不产生可控贡献（必失败），可用“特殊元素优先处理”：

先把所有 $1$ 位置安排并计数；
剩下的位置再乘上排列数补回。

下文“位置”均指 $1$ 的位置。

定义：

$w_i$ ：前 $i$ 个字符中 $0$ 的个数
$t_i$ ：前 $i$ 个字符中，有多少个 $1$ 位置最终无法录取
$v_i$ ：第 $i$ 个位置能录取所需的最小忍耐度

则：

$v_i=t_i+w_i$

Step 1：先看 $m=1$

当“录取人数超过 $1$ ”，可先算“全都录取不了”的方案数 $res$ ，再做：

$ans = |\Omega| - res,\qquad |\Omega|=n!$

令计数函数：

$S(p)=\left|\{x\mid c_x\le p\}\right|$

若记第 $r$ 个 $1$ 的原下标为 $pos_r$ ，则“全不录取”的乘法计数可写成类似：

$res=\prod_{r=1}^{k}\left(S(pos_r-1)-(r-1)\right)$

其中 $k$ 为 $1$ 的总数。

Step 2：出现反向限制，用容斥统一方向

枚举某个状态 $s$ （二进制表示哪些 $1$ 位置录取）：

若位置录取：要求 $v_i \le c_x$
若位置不录取：要求 $v_i > c_x$

两类条件方向相反，直接计数困难。定义事件 $A_i$ ：位置 $i$ “无法录取”。则需求为：

$\left|\bigcap_{i\in s}\overline{A_i}\right|$

利用补集与容斥：

$\left|\bigcap_{i\in s}\overline A_i\right| = |\Omega|-\left|\bigcup_{i\in s}A_i\right|$

注意空集合 $T=\varnothing$ 时：

$\bigcap_{i\in \varnothing} A_i = \Omega$

并写成标准容斥形式（含空集）：

$\left|\bigcap_{i\in s}\overline{A_i}\right| = \sum_{T\subseteq s}(-1)^{|T|} \left|\bigcap_{i\in T}A_i\right|$

做法：对每个状态 $s$ ，枚举其子集 $T$ ，计算 $\left|\bigcap_{i\in T}A_i\right|$ 并按 $(-1)^{|T|}$ 加减。

Step 3：把重复的子集枚举用 DP 计算

在 Step 2 中，很多量会被重复计算，因此用 DP 代替“对每个 $s$ 枚举所有 $T$ ”。

示例状态：

$dp_{i,j,k}: \text{前 } i \text{ 个 } 1 \text{ 中，} j \text{ 个钦定不录取，} k \text{ 个因容斥而不录取}$

把容斥求和结构嵌入 $dp$ 递推即可。

4. 最优性去状态

在最优化 DP 中，常可利用支配关系 / 单调性 / 等价路径删掉“不可能成为最优解”的状态，或只保留“代表状态”，从而降低复杂度。

例题：打家劫舍

设共有 $n$ 个房屋，第 $i$ 个房屋价值为 $a_i$ ，相邻房屋不能同时打劫。

状态定义：

$dp_i:\ \text{在前 } i \text{ 个房屋中，且打劫了第 } i \text{ 个房屋时的最大价值}$

转移：

$dp_i=\max_{x\le i-2}(dp_x)+a_i$

关键性质：

$dp_i \ge dp_{i-2}+a_i \ge dp_{i-2}$

因此：

与 $i$ 同奇偶的最大值一定在 $dp_{i-2}$
与 $i$ 异奇偶的最大值一定在 $dp_{i-3}$

从而：

$\max_{x\le i-2}(dp_x)=\max\big(dp_{i-2},dp_{i-3}\big)$

优化后转移：

$dp_i=\max\big(dp_{i-2},dp_{i-3}\big)+a_i$

只需维护少量历史状态即可。

例题 2：[NOIP2023] 天天爱打卡

题意：

一共有 $n$ 天，大 Y 可以花费 $d$ 的能量在任何一天跑步，但大 Y 不能在连续的 $k$ 天跑步。

此外，将给出 $m$ 段任务区间 $[l_i,r_i]$ 。如果在这段区间的每一天都跑了步，则会获得 $v_i$ 的能量。

大 Y 的初始能量为 $0$ ，请你最大化跑完步后大 Y 最终的能量。

思路：

有一个最朴素的状态设计方案就是 $f_i$ 表示考虑前 $i$ 天并且第 $i$ 天跑步的最大能量值，然后定义 $g_i = \max\limits_{j=1}^{i}f_{j}$

转移方程：

$f_i = \max_{j=i-k + 1}^{\,i} \left\{ g_{j-2} -(i-j + 1)\cdot d + \sum_{[l_p,r_p]\subseteq [j,i]} v_p \right\}$

这样子直接暴力转移的时间复杂度是 $O(nmk)$ 的。

可以想到，对于枚举的区间 $[j,i]$ ，能够贡献答案的任务区间 $[l_k,r_k]$ 一定满足 $j\le l_k\le r_k\le i$ 。

现在我们将区间 $[l_i,r_i]$ 看作是二位平面上的点 $(r_i,l_i)$ , 那么我们就能把后面的暴力求和变成求解二维平面上矩形的点权和，于是乎变成了一个基础的二维数点问题。

那么我们按照右端点顺序把任务区间加入，则 $r_k\le i$ 的条件就能天然满足。计算贡献时，我们就只需要查询满足 $l_k\ge j$ 的任务区间的权值和即可，这个可以用树状数组维护，单次计算贡献的复杂度降至 $O(\log m)$ ，整体时间复杂度 $O(nklog_{m})$

接下来考虑优化 $n$ ，由于最终的得分和完成的任务以及跑步的时间有关，因此会发现在一个区间开始或结束的时间开始跑步是一定不劣的，在一个区间的结束的时间完成跑步也一定不劣。因此我们的决策点就只有每个任务的 $l_i , r_i$ 两个点，这样就可以大大的减少状态数量，时间复杂度也就成了 $O(mklog_m)$ ，这就是通过最优性质来保留一定不劣的点，减少状态数。

最后，还剩下一个瓶颈没有解决：对于每一个端点都要枚举前 $k$ 个。所以我们需要接着优化 $dp$ 转移

转移为

$dp_i = \max_{\substack{1\le j\le i\\ p_i-p_j+1\le k}} \left\{ g_{\mathrm{pre}(j)} +\text{gain}(i,j) -\text{cost}(i,j) \right\}.$

另外，由于相邻关键天数之间可能存在空档天，需要区分“ $p_{j-1}$ 与 $p_j$ 是否相邻”：

$\mathrm{pre}(j)= \begin{cases} j-2, & j\ge 2\ \text{且}\ p_j=p_{j-1}+1,\\ j-1, & \text{否则}. \end{cases}$

最后有

$g_i=\max(g_{i-1},dp_i).$

接下来我们考虑从 $i \to i+1$ 的过程中，每个决策点的 $g_{pre(j)}$ 不变， $cost(i,j)$ 变化量一样， $gain(i,j)$ 的变化量取决于 $j$ 的大小，也就是说实际上这是一个区间修改+区间查询的问题，很自然想到用线段树来维护每个决策点 $g_{pre(j)} + gain(i,j) - cost(i,j)$ 的取值，然后在进行区间查询最值即可，查询范围可以双指针快速解决。时间复杂度为 $O(mlog_m)$

5. 最优性换维

把原来 DP 里“状态的一维”挪到“dp 记的值”里（或者反过来），从而：

把难维度（范围大/不好压）变成 dp 值（通常记最小/最大），
把好维度（范围小/可二分/只关心最左最右）留在状态里，
最终把复杂度从 O(大维度) 换成 O(小维度) 或 O(小维度 log …)。

具体而言：

你可以把 DP 看成一个函数：

原写法：

$f(\text{情况/状态}) = \text{在这种情况下最优的(最大/最小)值}$

例如：f[w] = 重量不超过 w 时最大价值
换维写法：

$g(\text{目标最优值}) = \text{要达到这个值，状态量至少/最多要多少}$

例如：g[v] = 达到总价值 v 所需的最小重量

但是，也不能无脑的进行换维：

因为你换维之后，经常会出现这种直觉陷阱：

你只保留了“达到某个值的最小资源”这一个最优信息；
但你必须证明：
以后做转移时，只需要知道这个“最小资源”就够了，不会因为丢了别的信息导致错过全局最优/合法性。

通常证明套路是：
对任意最优解，取“最后一步/最后一个物品/最后一段”，前面部分必然也是对应子问题的最优（否则就能替换得更好，矛盾）。

例题1：A94852.Knapsack 2

题意：n 个物品，每个有重量 w[i]、价值 val[i]，背包容量 W，最大化总价值。

常规 DP（容量当维度）

dp[cap] = 最大价值
复杂度 O(nW)，但如果 W 很大（比如 1e9）就炸了。

换维 DP（价值当维度）

令 S = sum(val)（如果价值和不大，比如 1e5），定义：

dp[v] = 达到总价值 v 的最小总重量
初始化：dp[0]=0，其他是 +inf
转移（倒序 v）：
dp[v + val[i]] = min(dp[v + val[i]], dp[v] + w[i])

最后答案是最大的 v，使得 dp[v] <= W。

这就是“定义域值域互换”：从“容量 -> 最大价值”换成“价值 -> 最小容量”。

例题2：LIS 最长上升子序列（“二分性/最左1”压维）

题意：给数组 a，求 LIS 长度。

常规 DP（ $O(n^2)$ ）

f[i] = 以 i 结尾的 LIS 最长长度

换维/压维写法（ $O(n log\ n)$ ）

定义：

dp[len] = 长度为 len 的上升子序列，其“最小可能结尾值”

性质：dp[len] 随 len 单调递增（或至少可二分定位）。
对每个 a[i]，找最大的 len 使得 dp[len] < a[i]，更新 dp[len+1]=min(dp[len+1], a[i])。

这里就是：

dp 值关于某一维具有二分性（能二分找位置），
或者“只需关注最左/右的 1”：
你可以把“能否形成长度 len”想象成一排 0/1，可行的 len 是前缀连续的 1，只要知道“最右的 1 在哪”就够了。

二、转移优化

在优化前先说明两种 $dp$ 转移类型

填表法 ( $dp_i \leftarrow \sum_{x=1}^{i-1}dp_{x}$ ) ，常规的，利用前方已知信息来直接求出$ dp_i$
刷表法 $(dp_{i+1} \leftarrow dp_{i+1}+dp_i)$ ，当你求出了 $ dp_i$ 时，将 $ dp_i$ 这个值分配到后续的 $dp$ 当中。

针对不同的转移类型，会有不同的转移优化，例如在填表法中常见的优化有前缀和，在刷表法中常见的优化有维护差分数组，刷表法常在计数类型动态规划中出现。

1.前后缀优化

此处不过多赘述，主要就是维护前缀/后缀的最值/总值/第k大，进而实现快速转移。

2.多步拆单步

知识点配图

类似于图论当中的“建虚点”，在此处可以通过建立另外的数组来记录值，然后进而快速转移，上文的前后缀优化也可以看作是多步拆单步。

3.倍增

倍增适用于转移轮数很大( $n = 10^9$ ) ，并且转移方程和转移轮数无关的情况，经典问题有各种矩阵乘法，完全背包。

例题：「NOI2020」美食家

4. ds 优化 dp 转移

根据转移方程选取合适的ds实现转移，例如上文[NOIP2023] 天天爱打卡： $f_i = \max\limits_{j < i}f_j + g(i,j)$ ，需要实现区间修改和区间最值，那么用线段树来实现快速转移会很合适。

5. 决策单调性优化

分治优化
Knuth 优化