专栏文章

线性 DP & 区间 DP & 树（环）形 DP 总结

ddaiyulong2024
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miom7t8k
此快照首次捕获于
2025/12/02 21:29
3 个月前
此快照最后确认于
2025/12/02 21:29
3 个月前
查看原文

一、线性 DP 总结

提醒
要认真阅读哦！

1. 定义

线性动态规划是一种动态规划方法，它在状态转移时具有线性的特征。线性 DP 通常适用于那些线性的问题，它的状态通常并没有很复杂，一般状态转移方程也很简单。但不排除特殊情况。
总结顺序
接下来我的总结将通过常规做题时思考的顺序进行总结。

2. 通用状态、答案、初值、转移与时间复杂度

状态

线性 DP 通常在定义状态时会设一个数组 dpdp，表示在目前第 ii 个阶段的最优解。
例如
令 dpidp_i 表示（在目前第 ii 个阶段的最优解）。

答案

由于状态时在目前第 ii 个阶段的最优解，所以答案通常是 dpndp_n，也就是算法进行到最后一个阶段的最优解。

初值

初值的设定并没有常规的设定，通常根据题目的一些要求及特殊性质进行设定。
例如最长上升子序列这一问题，根据这一题目的要求，就要设 dpi=1 (i∈[1,n])dp_i=1\ (i\in [1,n])。
但对于大部分题目来说，设 dp0=0dp_0=0 即可。

转移

提醒
转移时动态规划做题时思考的最重要步骤，如果你推导不出转移方程，那么极有可能时状态定义错误。
根据动态规划的最优子结构特性得出转移方程是需要依赖于前面的若干状态，而线性 DP 的转移具有线性的特征，所以转移方程通常形如 dpi=f(     … …     )dp_i=\text f(\ \ \ \ \ \dots\ \dots\ \ \ \ \ )。其中 ff 是某个函数，表示如何从前面的一个或多个状态得到当前状态的最优解。特殊的，其中一位的状态只是一个阶段的的情况，

时间复杂度分析

由于线性 DP 的转移通常是线性的，所以复杂度为 O(1)O(1)。但如果在转移时加入一些函数，则计算时间复杂度是需要考虑到这些函数。

二、区间 DP 总结

提醒
难度逐渐在提升哦！

1. 定义

区间 DP 是线性动态规划的扩展，主要处理一些区间合并等问题。它在分阶段地划分问题时，与阶段中元素出现的顺序 和 由前一阶段的哪些元素合并而来有很大的关系。

2. 性质

区间 DP 有以下特点：
合并：即将两个或多个部分进行整合，当然也可以反过来；
特征：能将问题分解为能两两合并的形式；
求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

3. 通用状态、答案、初值、转移、时间复杂度与代码

状态

由于区间 DP 求解的是区间合并的问题，则状态通常是：令 dpi,jdp_{i,j} 表示区间 [i,j][i,j] 的最优解（所有元素合并能获得的价值的最大值）。
提醒
在需要时可以在数组增加维度。

答案

区间 DP 的答案必然是 [1,n][1,n] 区间的答案，所以答案为 dp1,ndp_{1,n}。

初值

初值的设定并没有常规的设定，通常根据题目的一些要求及特殊性质进行设定。
对于大部分题目
设 dp0,0=0dp_{0,0}=0 即可。

转移

由于大多数区间 DP 求解的是区间合并的问题，容易得出 dpi,j=max⁡{fi,k+fk+1,j+cost}dp_{i,j}=\max \{ f_{i,k}+f_{k+1,j}+cost \}，其中 costcost 为将这两组元素合并起来的价值。

时间复杂度分析

由于区间 DP 的转移通常是需要三重循环的，所以基础复杂度为 O(n3)O(n^3)。
提醒
但如果在转移时加入一些函数，则计算时间复杂度是需要考虑到这些函数。
提醒
区间 DP 时间复杂度和空间复杂度均较高，请谨慎使用。

代码

C
int dp[N][N];	//dp[i][j] 表示区间 [i,j] 的最优解（所有元素合并能获得的价值的最大值）

// 初始化长度为 1 的区间
for(int i=1;i<=n;i++) {
	dp[i][i]=0;  // 单个元素通常代价为m0
}

// 按区间长度从小到大计算（长度从 2 到 n）
for(int len=2;len<=n;len++) {
	// 区间起点 i：从 1 到 n-len+1
	for(int i=1;i<=n-len+1;i++) {
		int j=i+len-1;  //区间终点 j
		dp[i][j]=INT_MAX/INT_MIN;   // 初始化为极 大/小 值（求最 小/大 值时）
		
		// 尝试所有分割点 k（i<=k<j）
		for (int k=i;k<j;k++) {
			// 当前分割的总代价 = 左区间代价 + 右区间代价 + 分割代价
			int cur=dp[i][k]+dp[k+1][j]+cost(i,k,j);
			
			// 更新最优解（求最大值时用 max）
			dp[i][j]=min/max(dp[i][j],cur);
		}
	}
}

cout<<dp[1][n];		//输出答案（通常为 [1,n] 的答案）

三、树（环）形 DP 总结

提醒
本部分虽然题目叫“树（环）形 DP 总结”，但是主要总结树形 DP。

1. 定义

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。

2. 通用状态、答案、初值、转移、时间复杂度与代码

通用状态

注意
树形 DP 主要关注以（         \ \ \ \ \ \ \ \ \ ）为根的子树。

状态

通常定义 dpu,kdp_{u,k} 表示以节点 uu 为根的子树中，在某种状态 kk 下的最优解。

答案

通常是根节点在特定状态下的最优解，即 best(dproot,k)\text{best}(dp_{root,k})。其中 best\text{best} 函数为求最优解函数，通常为 max⁡\max 或 min⁡\min。

初值

对叶子节点，根据具体问题设置初始状态值。

转移

对于非叶子节点，结合子节点的状态计算当前节点的状态，通常是 dpu,…=dp_{u,\dots}= 结合 dpv,…dp_{v,\dots}。

时间复杂度

通常为 O(n)O(n) 或 O(n×k)O(n\times k)，其中 nn 是节点数，kk 是状态数。

代码

C
vector<int> tree[N];	//使用邻接表构建树结构 
int dp[N][K]; 	//其中 N 为最大节点数，K 为最大状态数（通常为 2，因为通常状态只有 0/1）

void dfs(int id,int f) {	//其中 id 为当前搜索的节点，f 为 id 节点的父节点 
	//初值设定
	// ......
	// ......
	
	//转移：遍历 id 的子节点 son 
	for(auto son:tree[id]) {
		if(son==f) {	//如果儿子等于父亲，无效遍历 
			continue;
		} 
		dfs(son,id);	//继续搜索 
		
		//转移：通常分 k 种情况讨论
		dp[id][k1]=......;
		dp[id][k2]=......;
		......
		dp[id][kn]=......; 
	}
} 

dfs(0,-1);	//搜索从根节点开始，所以通常 id 初值为 0，根节点没有父节点，所以 f 为不存在的节点 -1

四、动态规划优化技巧

Success
如果不想要你的代码 TLE 或 MLE，那么就来看吧！

1. 状态定义优化

状态定义对于整个动态规划的思考过程有着无比重要的作用，修改状态定义会完全改变动态规划的思考思路，约等于“从头开始”。令人比较头疼的是，这类优化大多不具有通用性，即不能很套路地应用于多个题目中。因此，下文将从一个经典的例题出发，力求提供思路上的启发。

例（最长公共子序列 LCS）

题目大意
给定两个长度分别为 n,mn,m 且仅由小写字母构成的字符串 A,BA,B, 求 A,BA,B 的最长公共子序列。n≤106，m≤103n\le 10^6，m\le 10^3

朴素的解法

定义状态 fi,jf_{i,j} 为 AA 的前 ii 位与 BB 的前 jj 位最长公共子序列，则有
上述做法的时间复杂度 O(nm)O(nm)，无法通过本题。

更优的解法

我们仔细一想，发现了一个性质：最终答案不会超过 mm。
我们又仔细一想，发现 LCS 满足贪心的性质。
更改状态定义 fi,jf_{i,j} 为与 BB 前 ii 位的最长公共子序列长度为 jj 的 AA 的最短前缀长度（即将朴素做法的答案与第一维状态对调）
可以通过预处理 AA 的每一位的下一个 a,b,⋯ ,za,b,\cdots,z 的出现位置进行 O(1)O(1) 的顺推转移。
复杂度 O(m2+26n)O(m^2+26n)，可以通过本题。

2. 转移优化（单调队列 / 单调栈优化）

如果状态定义已经不能再优化，那么可以考虑优化转移。
动态规划优化转移的方法有很多，这里主要介绍单调队列 / 单调栈优化。

引入

单调队列主要用于维护两端指针单调不减的区间最值，而单调栈则主要用于维护前/后第一个大于/小于当前值的数。
注意
  • 求最小值要维护 单调递增/不减 的单调队列/单调栈，反之亦然。
  • 维护单调递增/递减比较时用 小于等于/大于等于，维护单调不减/不增比较时用 小于/大于。

单调队列优化具体步骤

  • 加入所需元素：向单调队列重复加入元素直到当前元素达到所求区间的右边界，这样就能保证所需元素都在单调队列中。
  • 弹出越界队首：单调队列本质上是维护的是所有已插入元素的最值，但我们想要的往往是一个区间最值。于是我们弹出在左边界外的元素，以保证单调队列中的元素都在所求区间中。
  • 获取最值：直接取队首作为答案即可。

单调栈优化具体步骤

  • 弹出非法栈顶：通过比较当前元素与栈顶的大小，弹出不满足单调栈性质的栈顶。以单调递增的栈（即栈顶最大，维护最小值）为例，将所有大于等于当前元素的栈内元素全部弹出。
  • 加入当前元素：将当前元素入栈即可。
 \
 \
 \
 \
引用内容的相关说明
本文章部分引用了 OI Wiki 的部分内容。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...