论 DP

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

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$。

对于 $P=1$，可以直接最短路。

如果 $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：注意到 $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$ 的字符串，想将其分成回文串的组合。请问你至少要分出几个字符串？

$n \le 3000$。

这个题目，设 $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$。

暴力做法是枚举所有的分割点，时间复杂度可能达到 $O(n!)$。

设 $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$。

首先有一个 $O(n^3)$ 的做法。

这个题很明显是 $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)$。

【例 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$。

算法 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)$。如果值域比较大，可以进行动态开点。