DP 论

· · 个人记录

本文大约 7 \times 10^3 个字，阅读起来大约需要 45 分钟。

DP 题目一般都是有 DP 的状态，状态转移方程和答案组成，我们每个 DP 的例题都会进行详解。DP 题比较灵活，每一题都有自己的转移方程，但大体可以归为几类。

【例 1】（01 背包问题）你有 n 个物品和一个载重为 m 的背包，第 i 个物品的重量为 w_i，价值为 v_i，求在重量限制下的价值最大和。

针对 30\% 的数据：n,m \le 20。

针对 50\% 的数据：n,m \le 50。

针对 100\% 的数据：n \le 1000,m \le 10000。

算法 1：

我会搜索（或我会状压）！考虑直接爆搜，选择每个物品是否选，再判断是否满足重量限制，时间复杂度 O(2^n)，可以通过 30 分。

算法 2：

我会剪枝！考虑剪枝，如果当前的重量 >m，那么就剪枝。这种叫可行性剪枝，如果最小的重量也大于 m，那么直接输出 0，可能通过 50 分。

算法 3：

我会 DP！我们设 dp_{i,j} 表示到第 i 个数，背包重量为 j 时的最大价值和，则 dp_{i,j}=dp_{i-1,k} （j<w_i），dp_{i,j}=\max(dp_{i-1,j}+dp_{i-1,j-w_i})（j \ge w_i）。时间复杂度 O(nm)，可以通过满分。

【例 2】（最长上升子序列）一个序列 a_1,a_2,a_3,\cdots,a_n，选出其子序列 b∈a，且 b_1<b_2<...<b_l，求 l 的最大值。

针对 40\% 的数据：n \le 20。

针对 100\% 的数据：n \le 10000。

算法 1：我会搜索！直接判断每个数选不选。

算法 2：我会 DP！假设 i 的上一个数为 j，j<i，则 a_j<a_i，dp_i=dp_j+1。

时间复杂度 O(n^2)。

思考题 n \le 10^6。

【例 3】（最长上升子序列计数）一个序列 a_1,a_2,a_3,\cdots,a_n，选出其子序列 b∈a，且 b_1<b_2<...<b_l，当 l 取最大值时有多少种方案。

针对 100\% 的数据：n \le 10000，答案在 long long 范围内。

很容易计算最长上升子序列长度，然后计数就是当 dp_{i}=dp_{j}+1 时 f_{i}=\sum f_{j}。

答案即为 f_n。时间复杂度 O(n^2)。

思考题 n \le 10^6。

【例 4】（最长公共子序列）有两个字符串 s,t，u∈s,v∈t 且 u=v，则称 u,v 为字符串 s,t 的公共子序列，求最长的公共子序列长度。

针对 10\% 的数据：|s| \le 10,|t| \le 10。

针对 30\% 的数据：|s| \le 20,|t| \le 20。

针对 100\% 的数据：|s| \le 2000,|t| \le 2000。

算法 1：我会暴力！直接枚举所有 s,t 的子序列，询问是否相等，时间复杂度 O(2^{|s|+|t|})，可以通过 10 分。

算法 2：我会优化！将 t 的子序列存入 set 中，然后每次判断是否 s 的子序列在 t 中存在，时间复杂度 O(|t|(2^{|s|}+2^{|t|}))，可以通过 30 分。

算法 3：我会 DP！设 f_{i,j} 表示 s 截止第 i 位，t 截止第 j 位的最长公共子序列，则答案为 f_{|s|,|t|}。状态转移：当 s 的第 i 位，t 的第 j 位相等时，变成 f_{i-1,j-1}+1，否则是在 f_{i-1,j}（即 s 串的上一位）和 f_{i,j-1}（即 t 串的上一位）中取较大的。

时间复杂度 O(|s||t|)。

思考题：|s| \le 2 \times 10^5,|t| \le 2 \times 10^5。

【例 5】（乘积最大）一个长度为 N 的数字串，用 K 个乘号分割，求分割成 K+1 个部分的乘积的最大值。

针对 30\% 的数据：1 \le N \le 18,1 \le K \le 4。

针对 100\% 的数据：1 \le N \le 40,1 \le K \le 6。

算法 1：我会暴力！直接爆搜每个乘号的位置，时间复杂度 O(N^K)，不可以通过。

算法 2：我会 DP！设 f_{i,j} 表示截止第 i 位用了 j 个乘号的最大乘积，则设上一个乘号用在 l 上，则 1 \le l \le j-1（显然），状态转移 f_{i,j}=\max(f_{l,j} \times s_{l+1,i})，其中 s_{i,j} 表示第 i 位到第 j 位所构成的数，注意会爆 long long/__int128，所以需要高精加、高精乘低精，高精乘高精，时间复杂度 O(N^4K)，瓶颈在于高精乘高精，若用 FFT 优化可以达到 O(KN^3 \log N)，可以通过 N \le 100,K \le 20 的数据。

上面几道例题都是普通 DP，下面我们正式开始讲 DP 优化。DP 优化有几个部分：（1）单调队列优化（2）数据结构优化（3）斜率优化（超过 S 组难度，不讲）。（4）滚动数组优化（5）前缀优化。

我们先讲单调队列优化。

【例 6】（选点问题）你有 n 个点，每个点都有价值 v_i，选择任意 m 个点（m 不固定）a_1,a_2,\cdots,a_m，使得对于任意的 2 \le i \le m，a_i-a_{i-1} \le k，求 \sum_{i=1}^m v_i 的最大值。

针对 10\% 的数据：1 \le k \le n \le 20。

针对 50\% 的数据：1 \le k \le n \le 10^4。

针对 100\% 的数据：1 \le k \le n \le 10^6。

算法 1：我会暴力！直接暴力枚举所有选的点（枚举子集），然后判断是否满足条件，时间复杂度 O(2^n)。

算法 2：我会 DP！设 f_i 表示选择第 i 个点的情况下，最大的价值和，则转移方程 f_i=\max_{j=\min(i-k,0)}^{i-1} f_j+v_i，时间复杂度 O(nk)。

算法 3：我会 DP 优化！注意到 f_i 转移的前一项就是一个长 k 的滑动窗口，所以只需要 O(n) 就可以处理，DP 的时候也是 O(n)，时间复杂度 O(n)。

数据结构优化也是很常用的方法。主要是依靠 O(n \log n) 的数据结构优化 DP，如线段树，BIT 等，但目前没有找到合适的例题。

接下来是滚动数组优化。

【例 7】同例 4，不过 |s| \le 3 \times 10^4,|t| \le 3 \times 10^4 且空间 512 M，时间 3s。

注意到 O(|s||t|) 的算法还是勉强可以过的，但是空间直接爆掉，注意到每个数只依赖于上、左、斜上三个数，所以每次只要开一个 2 \times |t| 的数组就可以了，转移方程也可以这样推，所以就可以通过这题。

这种方法就是滚动数组优化。

【例 8】（最大子段和）给出一个 n 和 n 个数的序列，求 L,R 使得 a_L+a_{L+1}+\cdots+a_R 最大，求出这个最大值即可。（各种优化）

针对 10\% 的数据：n \le 100。

针对 50\% 的数据：n \le 5000。

针对 100\% 的数据：1 \le n \le 2 \times 10^6，|x_i| \le 10^9。

算法 1：我会暴力！直接暴力枚举 [L,R] 并再用一重循环加上他们的和，时间复杂度 O(n^3)，拿到 10pts。

算法 2：我会前缀优化优化暴力！直接计算出每个数的前缀和并拿 s_R-s_{L-1} 取最大值，时间复杂度 O(n^2)，拿到 50pts。

算法 3：我会 DP！考虑 f_i 表示取第 i 个数的最大值，则答案等于 \max(f_i)，考虑转移：f_i 应该是只取 a_i 或取 a_{i-1} 这两种可能，所以状态转移就是 f_i=\max(f_{i-1}+a_i,a_i)，时间复杂度 O(n)。

还有一些其他的 DP，例如树形 DP，状压 DP。

状压 DP 有一道例题。

【例 9】（公司问题）已知 N 个点 M 条边的图和 P 家公司，第 i 条边用 [L,R,W,k] 表示，表示从第 L 个点到第 R 个点有一条边的权值是 W，且属于第 k 家公司，有 Q 个问询，询问从 u 到 v 经过最多 k 家公司的边的最短路，若走不到则输出 "NO WAY"。

针对 50\% 的数据：P=1。

针对 100\% 的数据：N \le 10^4,M \le 10^4,P \le 6,Q \le 2 \times 10^5。

算法 1：我会观察特殊性质！对于 P=1，可以直接最短路。

算法 2：我会状态压缩 DP！如果 P≠1，那么考虑状压每个经过公司的状态，转移方程为 dp_{i,v,S|(2^k)}=\min(dp_{i,v,S|(2^k)},dp_{i,u,S}+w)，其中 k 为当前边属于哪家公司，S 为状态，v 为 u 的邻居，dp_{i,j,S} 表示从 i 到 j 用 S 集合公司的最短路，最后求的时候直接暴力求出所有二进制位下 1 个数 \le k 的个数。

时间复杂度 O(2^Pm \log 2^Pm+q2^P)。

树形 DP 同样有一道例题。

【例 10】（独立集问题）一颗树，根为 rt，共 n 个结点，每个点都有点权，若 (u,v) 有边则 u,v 之间最多选一个，求最大点权和。

针对 20\% 的数据：n \le 20。

针对 100\% 的数据：n \le 10^5。

算法 1：我会暴力！直接暴力枚举所有子集，判断是不是独立集，然后计算点权和的最大值。

算法 2：我会 DP！记 dp_{u,0} 表示不选 u 的最大点权和，dp_{u,1} 表示选 u 的最大点权和，容易推出转移方程 dp_{u,1}=a_u+\sum_{v∈son_u} dp_{v,0}，dp_{u,0}=\sum_{v∈son_u} dp_{v,0}+dp_{v,1}，答案即是 \max(dp_{rt,0},dp_{rt,1})，其中 a_u 是 u 号的点权。

时间复杂度 O(n)。

【例 11】（合并石子）共有 n 堆石子，并成一堆，每次相邻合并的代价为两堆石子质量之和，求最小合并代价。

针对 20\% 的数据：n \le 10。

针对 100\% 的数据：n \le 500。

算法 1：我会暴力！直接暴力枚举合并顺序，时间复杂度 O(n!)。

算法 2：我会区间 DP！注意到 n \le 500，考虑 O(n^3) 的 DP。DP 分类中有一种叫区间 DP 的，时间复杂度都是 O(n^2) 到 O(n^3) 的。注意到 [i,k] 和 [k+1,j] 合并的代价为 sum_{i,j}，sum_{i,j} 代表 i 到 j 的质量之和，于是转移方程为 f_{i,j}=\min_{k=i}^j f_{i,k}+f_{k+1,j}+sum_{i,j}。

时间复杂度 O(n^3)。

【例 12】（回文串分割）你现在有一个长度为 n 的字符串，想将其分成回文串的组合。请问你至少要分出几个字符串？

算法 0：我会暴力！时间复杂度 $O(2^n)$，无法过任何一档分。 算法 1：我会 DP！这个题目，设 $f_i$ 为截止到 $i$ 的分出字符串最少个数，则 $f_i=\min f_j+1$，其中 $[j,i]$ 为回文串。回文串可以进行两边哈希，然后就可以 $O(1)$ 求了。 时间复杂度 $O(n^2)$。 【例 13】（异或和最大分割）你现在有一个长度为 $n$ 的序列，想分割为一系列序列，使得其异或和之和最大，求这个最大值。空间限制 128MB。 针对 $10\%$ 的数据：$n \le 10$。 针对全部数据：$n \le 8000$。 算法 0：我会暴力！暴力做法是枚举所有的分割点，时间复杂度可能达到 $O(n!)$。 算法 1：我会 DP！设 $f_i$ 为 $[1,i]$ 的分割分出的异或和最大值，则 $f_i=f_j+sum_{j,i}$，显然可以 $O(n^2)$ 预计算 $sum_{j,i}$，但空间需要 250MB。 观察到异或的一个性质：$[l,r]$ 的异或和 = $[1,r]$ 的异或和 异或 $[1,l-1]$ 的异或和，维护前缀异或和即可，时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。 【例 14】（最长回文串）给定一个长度为 $n$ 的字符串，求其最长回文子串。 $n \le 6000$。 针对 $30\%$ 的数据：$n \le 500$。 算法 1：我会暴力！首先有一个 $O(n^3)$ 的做法。 算法 2：我会区间 DP！这个题很明显是 $O(n^2)$ 的 DP 题，记 $f_{l,r}$ 为 $[l,r]$ 是否是回文串，则 $f_{i,i}=1$，若 $a_i=a_{i+1}$ 则 $f_{i,i+1}=1$ 否则 $f_{i,i+1}=0$。然后再算 $f_{l,r}$，若 $s_l=s_r$ 则 $f_{l,r}=f_{l+1,r-1}$，否则等于 $0$。 然后算答案枚举 $len$ 和 $l$，然后求出 $r$ 和对应 DP 值，并判断是否是 $1$ 即可。当然这题还可以双指针和哈希。 时间复杂度 $O(n^2)$。 该题还可以升级到 $n \le 2 \times 10^7$，在高级字符串中会讲到。 【例 15】（最长上升子序列）一个序列 $a_1,a_2,a_3,\cdots,a_n$，选出其子序列 $b∈a$，且 $b_1<b_2<...<b_l$，求 $l$ 的最大值。 针对 $40\%$ 的数据：$n \le 10000$。 针对全部数据：$n \le 10^6$。 算法 0：我会直接 DFS，时间复杂度 $O(2^n)$，可以拿到 0pts。 算法 1：我会暴力 DP，直接 $O(n^2)$ DP 上，可以拿到 40pts。 算法 2：观察该题的 DP 方程，显然可以进行权值线段树优化，$j<i$ 且 $a_j<a_i$，我们考虑在 $a_j<a_i$ 上做操作。我们每次在 $a_i$ 上加上 $f_i$，然后每次求就是求区间最大值，只要会单点修改区间求最大值的模板就可以了。 时间复杂度 $O(n \log n)$。如果值域比较大，可以进行动态开点。 接下来我们来讲一类特殊 DP，计数型 DP。 前面我们讲的许多都是最优化类型的 DP，现在我们将一些计数型 DP，包括他们的思路。 【例 16】（背包计数）有 $n$ 个物品和质量为 $m$ 的背包，每个物品最多选一次，质量为 $w_i$，求在满足质量之和不超过 $m$ 的情况下，能选出多少种不同的方案。 针对前 $50\%$ 的数据：$n \le 15$。 针对全部数据：$n \le 1000,m \le 10000$。 算法 1：我会暴力！$n \le 15$ 的情况可以直接爆搜得到结果，显然是 $O(2^n)$ 的。 算法 2：我会 DP！记 $f_{i,j}$ 表示前 $i$ 个物品和质量为 $j$ 的背包能装下的方案数。显然 $f_{i,j}=\sum f_{i-1,j-w_i}$，然后就完成了 $O(nm)$ 的转移。 总时间复杂度 $O(nm)$。 【例 17】（平均值子段计数）给定一个长度为 $n$ 的序列 $a_i$，求出平均值恰好为 $A$ 的子序列个数。 针对 $70\%$ 的数据：$n \le 20$。 针对全部数据：$1 \le n \le 50,1 \le A \le 50,1 \le a_i \le 50$。 算法 1：我会暴力！前 $70$ 分是送分题，直接爆搜，即可得到 $O(2^n)$ 的做法。 算法 2：我会 DP！记 $f_{i,j}$ 为选择 $i$ 个数，和为 $j$ 的方案数，则显然答案为 $f_{i,A \times i}$ 之和。转移非常显然，枚举 $k$ 并且通过 $k$ 转移，$f_{i,j}=\sum f_{i-1,j-a_k}$，初始化时 $f_{0,0}=1$，其余都是 $0$，这样就可以得到一个可以通过的 DP。 时间复杂度为 $O(n^2 \sum a_i)$，最大也就是 $O(n^4)$，$n \le 50$ 绰绰有余。 接下来讲几个 trick 或者 DP 的大方向，但是这些题目虽然知识点跟上面相仿，但难度会有所增加。也就是说，我们不再再在这种黄题以下有太多题目，而是主攻绿蓝紫 DP。 1.延迟计算。以下是例题。 【例 18】（NOIP 2025 T3 弱化/树的价值）一棵树的价值为其所有的节点的子树的点权之 $\operatorname{mex}$ 之和，现在可以为这棵树分配点权，求出树的价值的最大值。 针对 $5\%$ 的数据：$n \le 7$。 针对 $20\%$ 的数据：$n \le 40$。 针对 $50\%$ 的数据：$n \le 120$。 针对全部数据：$n \le 500$。 算法 1：我会暴力！注意到 $\operatorname{mex}$ 值是小于 $n$ 的，于是可以暴力 $O(n^n)$。 原题中还有些 $n \le 13$ 和 $n \le 18$，大概率是留给一些状压 DP 的。$n \le 13$ 可能是 $4^n$ 级别。 算法 2：我会优化！记 $f_{u,i,j}$ 表示 $u$ 的子树内 $\operatorname{mex}$ 为 $i$，有 $j$ 个 $>i$ 的数的树的价值最大值，剩下节点全部小于 $i$。 不妨把这个 DP 的转移看作两个子树的合并过程，则可以得到以下方程： $f_{u,\max(k_1,k_2),p_1+p_2} \gets f_{v,k_1,p_1}+f_{w,k_2,p_2}$。 现在是 $O(n^5)$ 的。很明显不能过，只能过 $n \le 40$。 算法 3：我还会继续优化！我们现在想象出这个模型，显然 $\operatorname{mex}$ 只能选 $k_1$ 或者选 $k_2$。假设选 $k_1$，枚举 $k_1$，不需要枚举 $k_2$，预处理 $g_{w,p}=\max f_{w,k,p}$，$f_{u,k_1,p_1+p_2} \gets f_{v,k_1,p_1}+g_{w,p_2}$。 现在是 $O(n^4)$ 的，可以过 $n \le 120$。 算法 4：我会估算正确复杂度！$p_1 \le sz_1$，$p_2 \le sz_2$，所以枚举 $v,w$ 和 $p_1,p_2$ 枚举量是 $O(n^2)$ 级别的，所以时间复杂度 $O(n^3)$，可以通过全部数据，在原题下可以获得 $48$ 分。 2.背包类 DP。 【例 19】（CSP-J 2025 T4/子序列计数）求出总共有多少种不同的 $a_i$ 的子序列方案，满足长度 $m \ge 3$ 且 $\sum_{i=1}^m l_i>2 \times \max_{i=1}^m l_i$。 针对 $40\%$ 的数据：$n \le 20$。 针对另外 $24\%$ 的数据：$l_i \le 1$。 针对 $68\%$ 的数据：$n \le 500$。 针对全部数据：$n \le 5000,a_i \le 5000$。 算法 1：我会暴力！针对 $n \le 20$ 显然可以暴力。 算法 2：我会组合数学！$l_i \le 1$ 可以推一下组合式子。 算法 3：我会 DP！考虑到每根木棍只能选一次，所以变成了 01 背包计数类题目。$f_j$ 表示长度为 $j$ 的方案数，注意到 $a_i \le 5000$，显然有 $O(n \times \max_{i=1}^n a_i)$ 的做法，或者说是 $O(nV)$ 的。非常显然。 时间复杂度 $O(nV)$。 3.树形 DP。 这边讲一下基环树上的一些 DP。 【例 20】（ZJOI2008/基环森林最优独立集）求一颗基环森林上的最优独立集的分数之和。 针对 $30\%$ 的数据：$n \le 20$。 针对 $100\%$ 的数据：$n \le 10^6$。 算法 1：我会暴力！正常暴力枚举然后判断是 $O(2^nn)$ 的，可以通过 $30$ 分。 然后你可以用一些神秘的 $O(n^2)$ 或 $O(n^3)$ 的做法做出一些其他分数。 算法 2：我会 DP！最后找正解：首先正常树形 DP 找最优独立集是显然有 $O(n)$ 解法的。然后考虑每次找一个基环树，先找环然后把它从中间剪开再分别用剪开的那条边 $(u,v)$，对 $u$ 和 $v$ 分别做一次树形 DP，最后找到最大值求和即可。 时间复杂度 $O(n)$。 4.图上 DP。 图上 DP 一般具有严重后效性，为解决这个问题，可以使用两种不同的方式： **A.进行 Tarjan 缩点缩成 DAG（有向无环图）后用拓扑排序法进行 DP，适用于数据范围较大的情况。** **B.用迭代法进行 DP，适用于数据范围较小的情况。** 每一种方法都有一道例题。 【例 21】（缩点）求出一个有向图上，每个点可以经过多次但只计算一次分数的最大可以拿到的点权和。 针对 $100\%$ 的数据：$n \le 2 \times 10^5,m \le 5 \times 10^5$。 考虑状态转移，记 $f_u$ 表示 $u$ 能拿到的最大点权和，则显然有状态转移方程 $f_v=\max f_u+a_v$。这个状态转移显然有后效性，考虑用 Tarjan 缩点至 DAG 即可解决。时间复杂度 $O(n+m)$。 【例 22】（最少金币数）有一个 $n$ 个点 $m$ 条边的网络，你正在从 $s$ 到 $t$ 的过程中，其中你每一次若不投金币，则你会随机游走，否则你可以指定一个目标，请问你到达 $t$ 的最少金币数。若不能到达输出 $-1$。 针对 $28\%$ 的数据：图是 DAG。 针对全部数据：$n \le 3000,m \le 3 \times 10^4$。 算法 1：我会观察特殊性质（DAG）！考虑状态，从后往前 DP，$f_u$ 表示从 $u$ 到 $t$ 的最少金币数。则显然 $f_u=\min(\max f_v,\min f_v+1)$。 算法 2：我会迭代！这个状态转移到一般图上显然有后效性。因为数据范围不大，且 $f_i \le n$。考虑迭代，分别考虑前面两种转移，然后在枚举 $f_v$ 取转移 $f_u$ 即可。 答案便是 $f_s$ 了。 时间复杂度 $O(nm)$。 5.分段/切割型 DP。 【例 23】（分段 mex 和最大值）给出一个序列，求出分割后每个区间 mex 值之和的最大值。 针对 $30\%$ 的数据：$n \le 20$。 针对全部数据：$n \le 2000$。 算法 1：我会暴力！第一档分是送分的。暴力枚举每个点是否是分割点，即可做到 $O(2^nn)$。 接下来我们来考虑正解。 算法 2：我会 DP！考虑 $f_i$ 表示 $[1,i]$ 的分割 mex 最大值，$j$ 为上一个分割点，即可得到方程 $f_i=\max f_j+w(j,i)$，$w(j,i)$ 表示 $j$ 到 $i$ 的 mex 值。 时间复杂度 $O(n^2)$。 其实这种类型的 DP 上文中也有提到，难度一般都在黄绿左右，一般都是 $O(n^2)$ 级别的。如果能优化，一般都是用线段树或者各类数据结构优化。笔者曾看过一道李超线段树+slope trick 优化一个分段 DP 的。大概难度已经到达紫。 关于 DP，就先讲这么多。 本文完。