yeyou26 的博客
浅谈动态规划
yeyou26 LV 6 @ 2025-7-2 17:29:57

DP 入门

序列 DP

LIS（最长严格上升子序列）

转移方程：

$$\begin{array}{ll} f_i=\max _{0\leq j<i, a_{j}<a_i} f_{j}+1 \end{array}$$

优化：
- 方式一：
  - 设 $g_{i}$ 表示结尾为 $i$ 的子序列的最大长度
  - 用 BIT 维护 $g_{i}$
  - 转移：查询 $g_{i}$ 前缀最大值，再单点修改 $g_{a_{i}}$
  - 时间优化到 $O(n\log \text{值域})$ ，需要 $O(值域)$ 的空间
- 方式二：
  - 设 $g_{i}$ 表示长度为 $i$ 的子序列的最小结尾
  - 转移：二分查询到最大的比 $a_{i}$ 小的 $g_{k}$ ， $f_{i}$ 即为 $k+1$ ，并用 $a_{i}$ ckmin $g_{k+1}$
  - 时间优化到 $O(n\log n)$
- 有的题只能用第一种，也有的只能用第二种，所以都要会

LCS（最长公共子序列）

转移方程：

$$\begin{aligned} f_{i, j}= \begin{cases}f_{i-1, j-1}+1 & \left(a_i=b_j\right) \\ \max \left(f_{i-1,j},f_{i,j-1})\right. &(otherwise)\end{cases} \end{aligned}$$

排列的 LCS：设 $g_{i}$ 表示 $a_{i}$ 在 $b$ 中的位置， $g_{i}$ 的 LIS 即为排列的 LCS

最大子段和

转移方程：

$$\begin{array}{ll} f_i= \begin{cases}f_{i-1}+a_i & \left(f_{i-1} \geqslant 0\right) \\ a_i & \left(f_{i-1}<0\right)\end{cases} \end{array}$$

最大不交区间价值和

$m$ 个区间，每个区间为 $\left[L_i, R_i\right]$ ，价值为 $V_i$ ，从中选出若干个没有交集的区间，求选出区间的最大价值和
区间按 $R_i$ 排序，设 $f_{i}$ 为前 $i$ 个区间的最优解。
转移：二分查找当 $k \in[1, i-1]$ 时满足 $R_k<L_i$ 的最大的 $k$ 值
转移方程：

f[i]=\max (f[i-1], f[k]+V i)

区间 DP

区间 DP 有以下特点：
- 可合并：能将两个或多个部分进行整合
- 可分解：能将问题分解为能两两合并的形式
- 常见求解方式：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，更新最优结果
破环成链：区间 DP 常用技巧，我们无法接受枚举环断点的复杂度，于是将环复制一份，序列长度变为环的二倍，转为序列 DP

背包 DP

约定： $v_{i}$ 表示第 $i$ 个物品的价值， $w_{i}$ 表示第 $i$ 个物品的代价

简单背包

01 背包

转移方程：

$$\begin{array}{ll} f_{i, j}=\max \left(f_{i-1, j}, f_{i-1, j-w_i}+v_i\right) \end{array}$$

一般压掉一维倒序枚举：

for (int i = 1; i <= n; i++)
    for (int j = m; j >= 0; j--)
        if (j >= w[i]) dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);

完全背包

转移方程：

$$\begin{array}{ll} f_{i, j}=\max \left(f_{i-1, j}, f_{i, j-w_i}+v_i\right) \end{array}$$

一般压掉一维顺序枚举：

for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++)
        if (j >= w[i]) dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);

分组背包

$n$ 组物品，每组最多选 $1$ 个
$cnt_i$ 表示第 $i$ 组物品个数

for (int i = 1; i <= n; i++)
    for (int j = m; j >= 0; j--)
        for (int k = 1; k <= cnt[i]; k++)
            if (j >= w[i][k]) dp[j] = std::max(dp[j], dp[j - w[i][k]] + v[i][k]);

多重背包

二进制分组：把每种物品拆成 $\log$ 个，然后 01 背包
单调队列优化：复杂度更优，但难推难懂且常数巨大大，大部分情况跑的还不如二进制分组，基本认为没有用（坑）

多维费用背包

for (int i = 1; i <= n; i++)
    for (int j = m; j >= w1[i]; j--)
        for (int k = m; k >= w2[i], k--)
            f[j][k] = std::max(f[j][k], f[j - w1[i]][k - w2[i]] + v[i]);

其他

混合背包：第 $i$ 个物品是啥就套用哪种背包的转移
输出方案：可以用 $g_{ij}$ 记录第 $i$ 个物品在容量为 $j$ 时是否被选，输出伪代码：

int v = V; 
for (从最后一件循环至第一件) 
	if (g[i][v]) {
		选了第 i 项物品; 
		v -= 第 i 项物品的重量;
	} 
	else 未选第 i 项物品;  
}

求装到某容量的方案数：以 01 背包为例，转移方程变为 $f_{j}=f_{j}+f_{j-w_{i}}$
求最优方案数：设 $g_{i,j}$ 为前 $i$ 个物品容量正好为 $j$ 的方案数，转移不难

for (int i = 1; i <= n; i++)
{
    for (int j = m; j >= w[j]; j--)
    {
        int tmp = std::max(dp[j], dp[j - v[i]] + w[i]);
        int c = 0;
        if (tmp == dp[j]) c += cnt[j];                      // 如果从dp[j]转移
        if (tmp == dp[j - v[i]] + w[i]) c += cnt[j - v[i]]; // 如果从dp[j-v[i]]转移
        dp[j] = tmp;
        cnt[j] = c;
    }
}

第 $k$ 优解：感觉没鸟用（坑）

树上背包

常见模板：01 背包，但是如果要选第 $i$ 个物品，则必须选其父链上所有物品
相当于对每个子节点做分组背包
朴素转移：

$$\begin{array}{ll} f_{u,j}=\max(f_{u,j},f_{u,j-w_{u}-k}+v_{i}+f_{v,k}) \end{array}$$

时间复杂度： $O(nm^2)$
空间复杂度： $O(nm)$
均摊优化：
- 令 $siz(u)$ 为以 $u$ 为根的子树内所有物品的重量之和，因此转移的两个内层循环（枚举 $u,v$ 的容量）的上界均可以对 $siz$ 取 $\min$
- 可以证明时间复杂度均摊 $O(nm)$
DFS 序优化：
- 核心思想：
  - DFS 序：对树做 DFS 遍历，这样每个子树对应 DFS 序上的一个连续区间
  - 线性DP：把树上的依赖背包问题转化为序列上的 DP，利用 DFS 序的连续性优化状态转移
- 状态定义：设 $f_{i,j}$ 表示 DFS 序的前 $i$ 个节点（即 DFS 遍历的前 $i$ 步）总代价不超过 $j$ 的最大价值
- 状态转移方程：
$$\begin{array}{ll}f_{i, j}=\max \left(f_{i+1, j-w_u}+v_u,f_{u+siz(u), j}\right)\end{array} $$
- 时间复杂度： $O(nm)$

for (int i = dfs_clock; i >= 1; i--) {
	int u = id[i];         // 当前节点
	for (int j = 0; j <= V; j++) {
		f[i][j] = f[i+siz[u]][j]; // 不选当前节点（跳过子树）
		if (j >= w[u])  // 选当前节点
			f[i][j] = max(f[i][j], f[i + 1][j - w[u]] + v[u]);
	}
}

联通性树上背包

完全背包，但是选的东西必须在给定的树上构成连通块
考虑转化为树上背包
考虑点分治，这样每一种树上连通块都对应以某个点为根开始的树上背包 dp，即连通块内在点分树上深度最小的点
考虑设计一种复杂度与 $n$ 相关的 dp
$f_{j}$ 表示当前用 $j$ 容量的最大价值
算法流程：
- 入 $u$ ，把 $f$ 复制一份存起来，表示不选 $u$ 情况
- 强制选一个物品，然后把剩下的物品二进制优化，做 01 背包逐个插入更新 $f$ ，复杂度为 $O(\log(\max(cnt_{i}))m)$
- 带着新的 $f$ 向子树 dp
- 回 $u$ ，用之前存起来的 $f$ 与当前的 $f$ 取 $\max$
时间复杂度 $O(nm\log n\log(max(cnt_{i})))$
感觉没啥用，属于偏怪难

树形 DP

换根 DP

需要以每个节点为根进行一系列统计
一般有两个过程：
1. 第一次扫描，任选一个节点为根节点，执行树形DP进行统计，自底向上转移
2. 第二次扫描，从第一次选择的根节点出发进行第二次 dfs，自顶向下更新每一个节点为根节点时的答案
是一种常用思想，没有固定套路

点覆盖/独立集/支配集

最小点覆盖

设 $f_{i,0}$ 表示不选节点 $i$ 时以 $i$ 为根的子树的最小点覆盖大小， $f_{i,1}$ 表示选节点 $i$ 时以 $i$ 为根的子树的最小点覆盖大小
状态转移方程：

$$\begin{array}{ll} \begin{array}{l} f_{i, 0}=\sum_{j \in \operatorname{son}(i)} f_{j, 1} \\ f_{i, 1}=1+\sum_{j \in \operatorname{son}(i)} \min \left(f_{j, 0}, f_{j, 1}\right) \end{array} \end{array}$$

最大独立集

设 $f_{i,0}$ 表示不选节点 $i$ 时，以 $i$ 为根的子树的最大独立集大小， $f_{i,1}$ 表示选节点 $i$ 时以 $i$ 为根的子树的最大独立集大小
状态转移方程：

$$\begin{array}{ll} \begin{array}{l} f_{i, 0}=\sum_{j \in \operatorname{son}(i)} \max \left(f_{j, 0}, f_{j, 1}\right) \\ f_{i, 1}=1+\sum_{j \in \operatorname{son}(i)} f_{j, 0} \end{array} \end{array}$$

最小支配集

$f_{i,0}$ 表示不选节点 $i$ ，且 $i$ 未被其子节点支配 时，以 $i$ 为根的子树的最小支配集大小（即 $i$ 必须被父节点支配）
$f_{i,1}$ 表示不选节点 $i$ ，但 $i$ 已被某个子节点支配 时，以 $i$ 为根的子树的最小支配集大小
$f_{i,2}$ 表示选节点 $i$ 时，以 $i$ 为根的子树的最小支配集大小（此时 $i$ 支配自身及其邻接点）
状态转移方程：

$$\begin{array}{ll} \begin{array}{l} f_{i, 0}=\sum_{j \in \operatorname{son}(i)} \min \left(f_{j, 1}, f_{j, 2}\right) \\ f_{i, 1}=\min _{k \in \operatorname{son}(i)}\left(f_{k, 2}+\sum_{\substack{j \in \operatorname{son}(i) \\ j \neq k}} \min \left(f_{j, 1}, f_{j, 2}\right)\right) \\ f_{i, 2}=1+\sum_{j \in \operatorname{son}(i)} \min \left(f_{j, 0}, f_{j, 1}, f_{j, 2}\right) \end{array} \end{array}$$

状压 DP

把状态压缩成（通常是二进制）整数的一类 DP

子集枚举

状压 DP 的问题中，经常需要遍历一个集合的所有子集的所有子集，这一过程被称为子集枚举

for (int m = 0; m <= (1 << n); m++) // 遍历 n 这一状态的子集 m
	for (int s = m; ~s; s = (s - 1) & m) // 遍历 m 这一状态的子集 s

时间复杂度为 $O(3^n)$
证明考虑二项式定理： $$\begin{array}{ll} \sum_{k=0}^n C_{n}^{k} 2^k=(1+2)^n \end{array}$$

插头 DP

（不会，坑）

计数 DP

是一种利用类似 DP 的记忆化搜索方法（与在狭义上的 DP，即最优化问题有一定区别），用于解决计数（以及求和）问题
本质上是组合数学，但一般不与 DP 做区分

组合数恒等式

恒等式	描述
$C_n^m = 0 \quad (n < 0,\ m < 0,\ m > n)$	不合法
$C_n^m = C_n^{n - m}$	选 $m$ 个等效于不选另外 $n - m$ 个
$C_n^m = \dfrac{n}{m} C_{n - 1}^{m - 1}$	分子分母分别补上对应系数
$C_n^m = C_{n - 1}^{m - 1} + C_{n - 1}^m$	帕斯卡定理，考虑选不选最后一个
$\sum_{i = 0}^n C_n^i = 2^n$	$n$ 个元素的所有子集；组合数的和；二项式定理 $(1 + 1)^n$
$\sum_{i = 0}^n (-1)^i C_n^i = [n = 0]$	二项式定理 $(1 - 1)^n$
$\sum_{k = 0}^n k \times C_n^k = n \times 2^{n - 1}$	组合数加权和；利用第二条恒等式推出
$\sum_{i = 0}^m C_n^i C_m^{m - i} = C_{n + m}^m$	范德蒙德卷积；每种选法与合并后选法一一对应
$\sum_{i = 0}^n {(C_n^i)}^2 = C_{2n}^n$	范德蒙德卷积在 $n = m$ 时的特殊情况
$\sum_{i = 0}^n C_i^m = C_{n + 1}^{m + 1}$	范德蒙德恒等式；枚举最后一个元素是哪个
$\sum_{i = s}^n C_i^m = C_{n + 1}^{m + 1} - C_s^{m + 1}$	范德蒙德恒等式引理；整体减去前缀

卢卡斯定理

对于质数 $p$ ，有 $C_n^m (mod\ p)=C_{n\%p}^{m\%p} C_{n/p}^{m/p}(mod\ p)$

long long Lucas(long long n,long long m)
{
    if(!m) return 1;
    return Lucas(n/P,m/P)%P*C[n%P][m%P]%P;
}

插板法

是一种思想，应用较广，用两个例题来理解
- 问题 1：有 $n$ $n$ 个完全相同的元素，要求将其分为 $k$ $k$ 组（组间有序），每组至少有一个元素，一共有多少种分法？
  - 转化问题， $n$ 个元素分成 $k$ 组，可以视作将 $n$ 个元素排成一列，然后在其中的 $n-1$ 个间隔中选择 $k−1$ 个间隔插入隔板，答案为 $C_{n-1}^{k-1}$
  - 也可以看作整数拆分方案数，即把 $n$ 拆分成不为 0 的 $k$ 个数的方案数
- 问题 2：有 $n$ $n$ 个完全相同的元素，要求将其分为 $k$ $k$ 组（组间有序），每组可以为空，一共有多少种分法？
  - 考虑每组“借”一个元素进来，就变成了 $n + k$ 个元素分成 $k$ 组，每组至少有一个元素的情况，原问题和新问题的解一一对应，答案相同，根据问题 1 得答案为 $C_{n+k-1}^{k-1}$
  - 同样可以看作把 $n$ 拆分为可以为 0 的 $k$ 个数的方案数
不难推广到每组至少有 $m$ 个元素的情况

容斥原理

$|S_1 \cup S_2 ∪ \cdots ∪ S_n|=\sum|S_i|-\sum|S_i\cap S_j|+\cdots+(-1)^{n-1}|S_1\cap S_2\cap \cdots \cap S_n|$
$|A_1∪A_2∪⋯∪A_n|=∑_{i=1}^n(−1)^{i−1}∑|A_1∩A_2∩⋯∩A_i|$
简单来说，就是对 $2^{n−1}$ 种非空的交集求和，系数为 $(−1)^{取出集合大小−1}$
证明:

$$\begin{aligned} Cnt=&|\{T_i\}|-|\{T_i\cap T_j|i<j\}|+\cdots+(-1)^{k-1}\left|\left\{\bigcap_{i=1}^{k}T_{a_i}|a_i<a_{i+1}\right\}\right|\\ &+\cdots+(-1)^{m-1}|\{T_1\cap\cdots\cap T_m\}|\\ =&\dbinom{m}{1}-\dbinom{m}{2}+\cdots+(-1)^{m-1}\dbinom{m}{m}\\ =&\dbinom{m}{0}-\sum_{i=0}^m(-1)^i\dbinom{m}{i}\\ =&1-(1-1)^m=1 \end{aligned}$$

数位 DP

特定的一类冷门计数 DP，时代的眼泪
这种问题比较好辨认，一般具有这几个特征：
1. 要求统计满足一定条件的数的数量（即，最终目的为计数）
2. 这些条件经过转化后可以使用「数位」的思想去理解和判断
3. 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制
4. 上界很大，暴力枚举验证会超时
没什么套路或可讲的，做点题大概就明白了

浅谈动态规划