dp 学习笔记

一.前言

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

其思想灵活多变，在 OI 中占有重要地位，必须掌握熟练。

二 背包问题

背包问题都类似以下形式：

• 每种物品都有一个价值 \(w\) 和体积 \(c\)，每种物品数量为 \(num\),有一个背包容积为 \(v\),用一些物品装背包使得物品总价值最大.

Part 1 01背包

最基础的一种背包。

模板中 $ num=1 $ 的情况。

用 \(dp_{i,j}\) 代表i件物品填充j体积的最大收益

可得方程 \(dp_{i,j}=max(dp_{i-1,j},dp_{i-1,j-c_i}+w_i)\)

例题：采药

Part 2 完全背包

模板中 $ num=\infty $ 的情况。

用 \(dp_{i,j}\) 代表i件物品填充j体积的最大收益

可得方程 \(dp_{i,j}=max(dp_{i-1,j},dp_{i-1,j-k\cdot c_i}+k\cdot w_i)\)

例题：疯狂的采药

Part 3 多重背包

模板中 \(num=n\) 的情况。

和完全背包一样的做法。

三.区间 dp

Part 1 概括

区间 dp 是一种比较另类的 dp。

一般情况下，dp 对象是一个区间。定义 \(dp_{i,j}\) 为对于区间 \([i,j]\) 的结果，通过若干子区间 \(dp_{l,r}\) 的 dp 值推出当前区间的值。

由于大多数求解顺序都是由小推大，所以应优先求解小区间，可以这么理解：

设当前穷举区间长度为 \(len\),则应先穷举 \(len=1\) 情况，再穷举 \(len=2\) 情况，然后是 \(len=3\) ，\(len=4\)……

Part 2 tricks

下文是一些常见的区间 dp trick。

trick1 石子合并流

经典的枚举分界点 \(k\) 套路。

例题：[NOI1995] 石子合并

对于 \(dp_{i,j}\)，枚举断点 ，则可得方程：

另外，由于序列是一个环，所以把序列复制一遍，破环为链。

（由于博主孤陋寡闻，博主没有想到更多trick）

四.状压 dp

五.树上 dp

树上 dp，顾名思义，是一种在树上进行的 dp。

其形式一般为这样：

void tree_dp(int x,int fa){//x为当前节点，fa为父亲节点 
	if(speical(x)){//某些题目存在关键点需要特殊处理 
		...;
	}
	for(int i=0;i<g[x].size();i++){
		int to=g[x][i];
		if(to==fa){//因为一般建的都是双向边，防止死循环 
			continue;
		}
		tree_dp(to,x);//优先转移儿子节点 
		dp[x]=...; //转移当前节点 
	}
	return;
}