DP 复习
Crsuh2er0
·
·
个人记录
线性 DP
顾名思义，线性状态动态规划指的是一类状态定义与题设内容线性相关的动态规划。
题设中有序列（数组），那动态规划的状态就是一维的；如果题设中有棋盘（网格、双序列）、那么动态规划的状态就是二维的。
线性状态动态规划定义状态的时候经常会考虑「某类有序事件中前若干个子事件的答案」。
一般来说，线性的状态最为直观，容易用有向无环图（DAG）表示，也比较容易理解。所以遇到动态规划问题构造状态时，通常会最优先考虑能否采用线性状态。
最大子段和
用 f[i] 表示以 i 为结尾的最大子段和，则
f[i] = \max(0,f[i - 1] + a[i])
显然,若之前的子段和 < 0 则不如新开一段好。
若之前的子段和 \ge 0 则接上更好。
带长度限制的最大子段和
考虑子段和是连续一段的和，所以它容易用前缀和求出。
所以当长度限制为 k 时，我们对序列做一遍前缀和，再用长度为 k 的单调队列维护最小前缀和，枚举即可。
LIS
$$f[i] = \max_{1 \le j < i,a[j] < a[i]}f[j] + 1$$
答案为 $\max_{1 \le i \le n}f[i]$。
直接做是 $O(n^2)$ 的。
考虑优化。
用 $d[i]$ 表示所有的长度为 $i$ 的上升子序列的末尾元素的最小值，则 $d[i] < d[i + 1]$。
初始化 $d[1] = a[1],len = 1$。
每次遇到一个新的 $a[i]$ 时，由 $d[i]$ 单调，直接二分查找位置放入 $a[i]$ 即可。若 $a[i] > d[len]$，则 $d[len \leftarrow len + 1] = a[i]$。
时间复杂度 $O(n \log n)$。注意 $d[i]$ 中存的**不是**方案。
### Dilworth 定理
[P1020 [NOIP1999 提高组] 导弹拦截](https://www.luogu.com.cn/problem/P1020)
将一个序列划分成若干个不升子序列的最小个数等于该序列 LIS 长度。
即，不升最小个数等于上升最大长度。
[Dilworth 定理与 LIS](https://zhuanlan.zhihu.com/p/598049983)
把整个序列最少需要划分成多少个子序列满足划分出的每个子序列都是不上升子序列，其实就是 Dilworth 定理的运用。
我们相当于求解偏序集($\ge$)的最少链划分，由定理可以得知，其就等价于求最长反链长度($<$)即序列的最长上升子序列的长度。
### 子序列提取问题
[P2285 [HNOI2004] 打鼹鼠](https://www.luogu.com.cn/problem/P2285)
$f[i]$ 表示只考虑前 $i$ 只老鼠，确定打第 $i$ 只老鼠的情况下，最多能打的老鼠数。
这里确定了第 $i$ 只老鼠被打，是为了**确定信息，便于转移**。
$$ f[i] = \max_{j < i,|x[i] - x[j]| + |y[i] - y[j]| \le t[i] - t[j]}f[j] + 1 $$
答案为 $\max_{1 \le i \le n}f[i]$。
比较两题解法，可以总结出「子序列提取」问题的常规思路：
考虑新加入的数与前面每个状态之间的关系与转移可行性，如果恰好转移只和相邻两数有关，那么就可以获得一个复杂度至多为 $O(n^2)$ 的 DP。
#### 子段划分问题
[P1874 快速求和](https://www.luogu.com.cn/problem/P1874)
这是一道同时具有「子段划分」和「背包」两个模型的题，既要考虑把原串划分成若干段，又要让它们的和等于目标数字。
因为不需要区分段的个数，只要最小化它，所以状态记录就是某个局面的最少加号。
记 $f[i][s]$ 为只使用字符串前 $i$ 位，达到数字和为 $s$ 的最少加号数。
那么考虑 $f[i][s]$ 的前驱，就只需要知道具体的「最后一段」，那么只要枚举这个「最后一段」的起点就行了。
记 $v[i][j]$ 为字符串从第 $i$ 位到第 $j$ 位代表的数值，则有状态转移方程：
$$ f[i][s] = 1 + \min_{j < i}f[j][s - v[j + 1][i]] $$
总结一下，子段划分的经典解法是**枚举新段的起点，与新段之前算出来的结果拼在一起**。
这样一般可以很容易地得到一个 $O(n^2)$ 的解法。
[P2679 [NOIP2015 提高组] 子串](https://www.luogu.com.cn/problem/P2679)
从题面出现的元素来说，这是一道双序列子段划分问题。
综合前面的经验看，既然说要在字符串 $A$ 取出 $k$ 段来匹配字符串 $B$，最好把子段数和两个序列的位置都放在状态的定义里：
记 $f[k][i][j]$ 表示字符串 $A$ 以第 $i$ 个字符结尾取出 $k$ 段后，在字符串 $B$ 恰好匹配到 $j$ 的方案数。
先考虑最朴素的转移：首先看起来 $f[k][i][j]$ 大部分情况下都是 $0$，除非 $A[i] = B[j]$。
那么问题在于，$A[i] = B[j]$ 时会发生什么。
情况很简单：$A[i]$ 要么跟在上一段后面，要么新起了一段。
情况一比较简单，既然段数没变，那么前驱的段数还是保持 $k$，前驱在字符串里的指针也应刚好是 $i - 1,j - 1$。
但是情况二就会稍微复杂一点了。前驱的段数是 $k - 1$，在字符串 $B$ 里的指针是 $j - 1$，但是在字符串 $A$ 里的指针可以追溯到 $i$ 之前任何一个位置。
因为状态已经是 $O(nmk)$ 级别的了（甚至已经 MLE），转移必须 $O(1)$，所以需要一个辅助数组来记录 $f$ 在第二维上的前缀和：
用 $g[k][i][j]$ 表示取出 $k$ 段后，字符串 $A$ 在 $i$ 之前结尾，字符串 $B$ 匹配到 $j$ 的方案数。
很明显，这里 $g$ 是 $f$ 在第二维上的前缀和，即 $g[k][i][j] = \sum_{x = 1}^if[k][x][j]$。
这样新起一段的时候，直接用 $g[k - 1][i - 1][j - 1]$ 就能获得所有合法前驱，即 $O(1)$ 转移。
因为三维数组 MLE，但是 $k$ 这一维只与上一阶段有关，所以可以用滚动数组降低空间复杂度。
## LCS
[AT_dp_f LCS](https://www.luogu.com.cn/problem/AT_dp_f)
仿照线性 DP 的方程一般表示方法：
用 $f[i][j]$ 表示字符串 $a$ 前 $i$ 个字符与字符串 $b$ 前 $j$ 个字符的 LCS 长度。
考虑 $f[i][j]$ 的来源：
- 若 $a[i] = b[j]$ 则 $a[i],b[j]$ 显然在 LCS 中，$f[i][j] = f[i - 1][j - 1] + 1$。
- 若 $a[i] \ne b[j]$ 则 $a[i],b[j]$ 显然不匹配，$f[i][j] = \max(f[i - 1][j],f[i][j - 1])$。
最终答案为 $f[n][m]$。
注意到：
$a[i] = b[j]$ 时，$f[i][j] = f[i - 1][j - 1] + 1 \ge f[i][j - 1],f[i - 1][j]$。
$a[i] \ne b[j]$ 时，$f[i][j] = \max(f[i][j - 1],f[i - 1][j]) \ge f[i - 1][j - 1]$。
所以转移方程也可以写成
$$f[i][j] = \max(f[i][j - 1],f[i - 1][j],f[i - 1][j - 1] + [a[i] = b[j]])$$
### 排列上的 LCS
[P1439 【模板】最长公共子序列](https://www.luogu.com.cn/problem/P1439)
对于两个排列的 LCS，可以使用一个技巧将它转化为 LIS：
假定其中一个排列有序（做一个 $a_i \rightarrow i$ 的映射），并以 $a$ 的映射为基准替换 $b_i$。
这样，问题就转化为一个排列和一个 $1 \sim n$ 的排列的 LCS。
显然，$b$ 的 LIS 即为答案。
## 升维/降维
有时候有两个条件相互影响，且十分混杂，**不好分类（进行转移）**。此时考虑升维。
有时候有两个维度相互影响，且十分混杂，**不好分类（进行转移）**。此时考虑降维。
[P1544 三倍经验](https://www.luogu.com.cn/problem/P1544)
$f[i][j][k]$ 表示从第 $i$ 行第 $j$ 列出发到最底层，恰好使用 $k$ 次乘 $3$ 的最大数字和。
$$f[i][j][k] = \max(f[i + 1][j][k] + a[i][j],f[i + 1][j + 1][k] + a[i][j],f[i + 1][j][k - 1] + 3a[i][j],f[i + 1][j + 1][k - 1] + 3a[i][j])$$
[P1004 [NOIP2000 提高组] 方格取数](https://www.luogu.com.cn/problem/P1004)
首先考虑存储状态。先想到的一般是 $f[i][j][k][l]$ 来表示路径 $1$ 走到 $(i,j)$，路径 $2$ 走到 $(k,l)$ 的状态。
那想想怎么解决一个格子过两遍只能收益一次的问题。按照这个状态，没法知道在某个状态，一个点有没有被路径 $1$ 或者路径 $2$ 遍历过。
但可以知道，如果一个点被遍历了两遍，那么这个点是同时被两条路径遍历的。这建立在两条路径同时增加一步的基础上，因为可以想象，只要每次都走一步，那每个时刻都满足 $i + j = k + l$。
从这个角度看，一来有状态的冗余，二来用 $i + j = k + l$ 可以解决上一段提到的「过两遍」问题。现在所有路径都是等长的，只要处理好两条路径走到同一个点的事件就能放心转移了。
$s = i + j = k + l$，相当于是走过的步数（加 $2$）。
用 $f[s][i][k]$ 表示走了 $s - 2$ 步后路径 $1$ 在第 $i$ 行（第 $s - i$ 列），路径 $2$ 在第 $k$ 行（第 $s - k$ 列），就能不带冗余地表示出所有状态了。
容易转移。
## 计数 DP
[P2842 纸币问题 1](https://www.luogu.com.cn/problem/P2842)
$f[i]$ 表示凑出 $i$ 元最少使用的纸币张数。
$$f[i] = \min(f[i],f[i - a[i]] + 1) $$
正序转移。
[P2840 纸币问题 2](https://www.luogu.com.cn/problem/P2840)
考虑上楼梯一题的方案数与排列有关，因此我们考虑转化问题为上楼梯。
然后这题就做完了。
[P2834 纸币问题 3](https://www.luogu.com.cn/problem/P2834)
问的是组合方案数，而它只与每张纸币的使用数量有关。
$f[k]$ 表示凑出金额 $k$ 的方案数。
对第 $i$ 种纸币，进行类似完全背包的正序转移。
然后此题就做完了。
[U505981 整数划分](https://www.luogu.com.cn/problem/U505981)
如果直接套上纸币问题的话，复杂度为 $O(n^2)$，会超时。
用 $f[i][j]$ 表示一共使用了 $i \ (i \le \sqrt n) $ 个正整数，和为 $j$ 的方案数。
考虑极端原理。将 $f[i][j]$ 中的集合按照是否含有 $1$ 进行分类。
对于没有 $1$ 的集合，我们把集合中所有数减去 $1$，则它们与 $f[i][j - i]$ 中的集合一一对应。
对于有 $1$ 的集合，我们把 $1$ 删去，再将集合中所有数减去 $1$，则它们与 $f[i - 1][j - i]$ 中的集合一一对应。
由「一一对应」易知，结果不重不漏。
时间复杂度 $O(n \sqrt n)$。
## 背包 DP
### 01 背包
[P1048 [NOIP2005 普及组] 采药](https://www.luogu.com.cn/problem/P1048)
用 $f[i]$ 表在 $i$ 的时间内能采集到草药的最大价值。
$$ f[i] = \max(f[i],f[i - c] + v) $$
倒序转移。
最终答案为 $f[n]$。
复杂度 $O(nV)$。
#### 带依赖的 01 背包
[P1064 [NOIP2006 提高组] 金明的预算方案](https://www.luogu.com.cn/problem/P1064)
其实大致框架和普通 01 背包是相同的，只需要二进制枚举每个附件选不选进行转移就可以了。
每个物品附件数为 $att$，则复杂度为 $O(n2^{att}V)$。
#### 一种特殊的二维 01 背包 & 物品价格为负数的 01 背包
[P2340 [USACO03FALL] Cow Exhibition G](https://www.luogu.com.cn/problem/P2340)
考虑以一个维度为价格，一个维度为价值，直接跑 01 背包。
如果一个物品价格 $< 0$，那么转移需要与正常的 01 背包反着跑，并且要注意特殊边界的处理。
最终对每一个 $> 0$ 的价格和 $> 0$ 的价值，枚举符合这样条件的最大价格价值和即可。
考虑为什么这样枚举能得到这个最大和。对每一个价格，我们都得到了它的最大价值，即把它的所有可能价值取了最大值，把二维压缩成了一维。
所以这样枚举相当于在一维上枚举最大值，显然是可以的。
### 完全背包
[P1616 疯狂的采药](https://www.luogu.com.cn/problem/P1616)
用 $f[i]$ 表在 $i$ 的时间内能采集到草药的最大价值。
$$ f[i] = \max(f[i],f[i - c] + v) $$
正序转移。
最终答案为 $f[n]$。
注意答案最大为 $ta_i = 10^{11}$。
复杂度 $O(nV)$。
### bitset 优化可行性背包
[P2392 kkksc03考前临时抱佛脚](https://www.luogu.com.cn/problem/P2392)
理想情况下时间为 $\frac {sum} {2}$，所以我们需要让时间尽可能接近 $\frac {sum} {2}$。
即需要找到最接近 $\frac {sum} {2}$ 的可行解。
$f[i]$ 表示达到 i 的时间是否可行。
$$f[i] = f[i] \lor f[i - t] $$
不难发现可以用 bitset 优化转移。
复杂度 $O(\frac{nV}{w})$。
### 多重背包
#### 二进制优化
[P1833 樱花](https://www.luogu.com.cn/problem/P1833)
如果把多重背包每个物品直接拆成一个，套上 01 背包的话，复杂度 $O(npV)$，会超时。
考虑对物品数量进行二进制拆分。例如将 $9$ 拆分为 $1,2,4,2$，可以用这四个数组合起来的和表示出 $0 \sim 9$ 任意一个数。
通过这样的拆分，我们可以把多重背包复杂度优化到 $O(nV \log p)$。
#### 单调队列优化
有点复杂，暂时不想写。
# 区间 DP
囿于问题本身限制，「某类有序事件中前若干个事件的子答案」不再能支撑状态转移，我们需要寻找「从某个元素起到另一个元素结束所包含所有连续元素的子答案」作为状态。
在这个描述下，每个状态会对应与原题序列上一个区间。
区间具有良好的性质：
- 短的区间可以拓宽成长的区间。
- 相同长度的区间互相不包含。
这样，可以把所有状态理解成 DAG，即不会有可以互相到达的局面。基于这个原则，可以思考如何构造转移。
[P1435 [IOI2000] 回文字串](https://www.luogu.com.cn/problem/P1435)
初看此题感觉难以下手。
我们考虑很简单的情况。
- `aa` 已经是一个回文串了。
- 要把 `qaa` 变成回文串，只需要变为 `qaaq`。
- 要把 `aqaqas` 变为回文串，只需要变为 `saqaqas`。
发现规律：考虑区间左右拓宽 $1$ 带来的影响。
1. 先把 $S[1,n-1]$ 变为回文串，再把 $S[n]$ 接在右边。
2. 先把 $S[2,n]$ 变为回文串，再把 $S[1]$ 接在左边。
3. 如果 $S[1] = S[n]$，那么只需要把 $S[2][n - 1]$ 变成回文串。
$f[i][j]$ 表示将 $S[i][j]$ 变为回文串至少需要插入的字符数。
1. $S[i] = S[j]$ 时
$$f[i][j] = \min(f[i][j - 1] + 1,f[i - 1][j] + 1,f[i - 1][j + 1]) $$
2. $S[i] \ne S[j]$ 时
$$f[i][j] = \min(f[i][j - 1] + 1,f[i - 1][j] + 1) $$
[CF607B Zuma](https://www.luogu.com.cn/problem/CF607B)
定义 $f[i][j]$ 表示将子串 $S[i...j]$ 清空所需最少步数。接下来思考如何转移。
1. 整个串自身是个回文串，可以通过比较 $S[i]$ 和 $S[j]$ 与 $f[i + 1][j - 1]$ 判断。（也可以预处理判断）
2. 可以把区间 $[i,j]$ 分成 $[i,k]$ 和 $[k + 1,j]$，分别利用这两个区间的答案。
3. 一个可消除串夹在另一个可消除串里。
对于第三种情况，不难发现若 $S[i] = S[j]$，那么其对消除次数无影响。
注意到任何一个串在完全消除的前一步一定是一个回文串，所以我们可以把 $S[i+1...j-1]$ 变为回文串，再将它们整个消去。
三种情况都容易转移。
像这样以区间左右端点来描述状态，一个状态由比它更小的其他状态转移而来的 DP 方法称为**区间 DP**。
转移时，考虑区间边界上的变化，边界条件一般是最小单位的区间（即 $i = j$ 的情况下）。
当不是很好构建转移顺序时，可以考虑使用记忆化搜索实现。
## 环形 DP
[P1880 [NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880)
可以证明一定存在一个「断点」在某两个相邻石子间，对于任意环上合并方式，都不会跨越这个断点进行合并。
因此，可以将环断成链进行处理。
将这个序列复制一次，变为长度为 $2N$ 的序列。其中每一个长度为 $N$ 的子段都是剪开的一条链。剩下的事情就和上例一样进行 DP 了。
[U506669 环上最大子段和](https://www.luogu.com.cn/problem/U506669)
环的常见处理方式是复制一倍，再当成区间问题解决。
但复制一倍后无法利用上题思路转移，处理的虚拟子段经常超过 $n$，这明显是非法情况。
现在考虑答案的情况：作为答案的子段要么经过 $n - 1$ 的分界线；要么不经过刚好是非环上序列的最大子段和。
考虑前者答案的性质：最大子段和经过 $n - 1$ 的分界线，那么它在环上的补集恰是非环上序列的最小子段和。
获得了这个喵喵的性质，便可以得知最终答案就是非环情况的最大子段和或者最小子段和的补段和。
所以，当在环上处理子段时，可以考虑它的补段。
# 树上 DP
## 换根 DP
## 图上 DP
# DP 优化
## 状态优化
### 降维
最经典的是每次读取的都是上一行的数据，例如背包问题优化掉一维，还有 LCS 优化掉一维。
经典技巧是滚动数组降低空间复杂度。
[P1541 [NOIP2010 提高组] 乌龟棋](https://www.luogu.com.cn/problem/P1541)
滚动数组最好用下标的切换实现，否则容易被卡常。
### 状态压缩（状压 DP）
状态压缩是一种状态优化技巧。
当我们发现 DP 的状态中需要存储一个 $01$ 序列时，考虑将序列压成一个整数进行存储。
### 倍增
如倍增求 LCA。
$u$ 的 $2^k$ 级祖先就是 $u$ 的 $2^{k-1}$ 级祖先的 $2^{k-1}$ 级祖先。
[P3147 [USACO16OPEN] 262144](https://www.luogu.com.cn/problem/P3147)
倍增好题。而且有点思维量。
首先题目要求一个低于 $O(n^2)$ 的解法。
观察发现序列中的值最终 $\le 58$。这个东西能用来干什么呢，难道要塞进状态里边吗？
以下「区间」均为左闭右开。
$f[i][v]$ 表示以 $i$ 为左端点，能合并为 $v$ 的区间右端点位置。
$$ f[i][v] = f[f[i][v - 1]][v - 1]$$
然后这题做完了。
复杂度 $O(n \log n)$。
## 转移优化
### DS 优化转移
#### BIT
可以使用权值树状数组对 LIS 进行优化。
回顾 LIS 的状态转移方程：
$$f[i] = \max_{1 \le j < i,a[j] < a[i]}f[j] + 1$$
可以看到 $\max$ 有两个限制，$j < i$ 和 $a[j] < a[i]$。
如果考虑上时序，那么 $j < i$ 自然满足。
把 $a[i]$ 想象成某个数组的下标，$f[j]$ 想象成记录在那个数组里的数。
现在需要这样一个 DS：
- 查询前缀最大值。
- 将某个位置的数与一个给定数取最大值。
由于需要的仅仅是维护前缀最值，而记录前缀信息恰恰是树状数组最原始的功能，所以直接树状数组维护。
查询时，寻找 BIT 中下标不超过 $a[i]$ 的最大元素。
更新时，将 $f[j]$ 写到 $a[i]$ 所在的位置。
# 技巧
[P3147 [USACO16OPEN] 262144 P](https://www.luogu.com.cn/problem/P3147)
如果发现状态转移方程里有某个条件（如 $a = b$），那么可以尝试把条件作为一个维度。
# Reference
深进「第四部分 动态规划」的部分内容