dp一遍通

zcxnb / 2024-10-23 / 原文

前言

马上csp-s考试了，却发现自己dp太菜了，打算恶补dp

线性dp理解

递推/记忆化搜索，有很多种理解方式
递归重叠子问题的记忆化搜索：

像这里例如 $f[3]$ 可以通过一次计算得到，保存答案，下一次直接调用即可，省去很多复杂度

我们从此引出dp第一个性质：最优子结构
大问题的最优解包含小问题的最优解，并且小问题的最优解可以推导出大问题的最优解

递推：
我们不管dp[i-1]是多少，但可以从dp[i-1]推导得出dp[i]

dp第二个性质：无后效性
未来与过去无关

dp实现方法

自顶而下：大问题拆解成小问题求解
常用递归+记忆化实现
自底而上：小问题组合成大问题求解
常用制表递推实现
这是最常见的dp方法

背包dp

0/1背包

状态设计

$dp[i][j]$ 表示只装前i个物品，体积为j时的最大价值

转移方程

$c[i],v[i]$表示第i个物品的体积和价值

方式1：

\[dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]) \]

方式2：

\[dp[i+1][j+w[i+1]]=max(dp[i+1][j+w[i+1]],dp[i][j]+v[i+1]) \]

区别：

方式一是通过上一维来推导这一维，方式二是通过这一维推导下一维

滚动数组

因为看到 $dp[i][]$ 这一维只与 $dp[i-1][]$ 这一维有关，所以可以压掉一维，优化空间

交替滚动

用 $dp[1][]$ 和 $dp[0][]$ 交替滚动，逻辑清晰，建议初学者食用

int dp[2][N];
int now=0,old=1;
for(int i=1;i<=n;i++){
	swap(now,old);
	for(int j=0;j<=C;j++){
		if(j>=w[i])  dp[now][j]=max(dp[old][j],dp[old][j-w[i]]+c[i]);
		else  dp[now][j]=dp[old][j];
	}
}

自我滚动

int dp[N];
for(int i=1;i<=n;i++){
	for(int j=C;j>=w[i];j--){
		dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
	}
}

注:j应该反过来循环，因为要保证 $dp[j-w[i]]$ 这一位还是商议维的答案，没有被覆盖掉
规律：只要这一位（i这一位）修改的地方已经用过了，不会再用了，就对答案无影响

分组背包

把物品分为n组，每组只能选一个
只要每组枚举选哪个，0/1背包哪组选或不选就完了

多重背包

规定每种物品有 $m_i$ 个

暴力解法

把每个物品看成一个独立的物品进行0/1背包

二进制优化多重背包

将 $m_i$ 按2的倍数从小到大拆，最后是一个小于或等于最大倍数的余数，相当于1个k，2个k，4个k...这些物品进行0/1背包，便可组合出选 $0~m_i$ 个k的情况，为什么呢，我们看一组例子

在这组例子中，相当于用 $1k,2k,4k,3k$ 的组合方案来代替 $0~10k$ 的组合方案，复杂度 $O(C\sum_{i=1}^n\log_2m_i)$

单调队列优化多重背包

复杂度更优，待填坑

最长公共子序列

设 $dp[i][j]$ 表示序列 $X_{0~i}$ 和序列 $Y_{0~j}$ 的最长公共子序列长度
当 $x_i==y_j$ 时：$dp[i][j]=dp[i-1][j-1]+1$
当 $x_i!=y_j$ 时：$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$
复杂度 $O(N^2)$,不是最优解

最长上升子序列

设 $dp[i]$ 为长度为i的最长上升子序列，最后一个数的大小
对于每一个 $a[i]$ 找到最大一个 $dp[j]<a[i]$ 使 $dp[j+1]=min(dp[j+1],a[i])$
这个过程可以用二分加速，复杂度 $O(N\log_2N)$

P2758 编辑距离

子问题：将 $X_{1...i}$ 转换成 $Y_{1...j}$ 的最小操作次数
状态设计： $dp[i][j]$ 为将 $X_{1...i}$ 转换成 $Y_{1...j}$ 的最小操作次数
状转方程：
当 $X_i==Y_i$ 时：$$dp[i][j]=dp[i-1][j-1]+1$$
当 $X_i!=Y_i$ 时：$$dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1$$
$dp[i-1][j-1]$ ：替换 $X_i$ 为 $Y_i$

$dp[i][j-1]$ ：删除 $X_i$

$dp[i-1][j]$ ：在i位置插入 $Y_i$

最小划分

给一个正整数组，把它分为s1,s2两部分，然后求最小的 $|s1-s2|$
考虑一部分划分越接近 $sum/2$ 越优，然后0/1背包做就可以了

树形dp

树上做dp非常常见，因为树本身有子结构性质（树和子树）
一般解题思路：先把树转化为有根树（如果不连通的树，就加一个虚拟根，它连接所有孤立的树），然后在做dfs，递归到叶子节点，再一层层返回信息，就在这一步做dfs

P2015 二叉苹果树

定义状态 $dp[u][j]$ 表示以节点u为根的子树上留j条边时

二叉树做法

考虑左右节点的边的总数是一定的，所以我们枚举一个子树的边就可以了

void dfs(int u){
	for(int i=0;i<=num;i++){//num代表子树内边的数量
		dp[u][i]=max(dp[u][i],dp[lson][i],dp[rson][num-i]);
	}
}

多叉树做法

我们挨个子节点枚举，然后再枚举当前子节点v选的边数，剩下的就是1~v-1 的子节点保留的分叉数

void dfs(int u){
	for(auto v:b[u]){//v是u的子节点
		for(int i=num;i>=1;i--){//枚举要割几条边
			for(int j=0;j<=i;j++){
				dp[u][j]=max(dp[u][j],dp[u][i-j-1]+dp[v][j]+w[u]);//i-j-1因为连向v也算一条边
                //实际上是dp[u][v][j]=max(dp[u][v][j],dp[u][v-1][i-j-1]+dp[v][j]+w[u]压掉v一维所以枚举i时要倒叙枚举
			}
		}
	}
}

P1352 没有上司的舞会

典题，不多赘述

状压dp

应用背景以集合为状态，集合一般可以用二进制表示，用二进制的位运算处理
集合问题一般是指数复杂度的，例如：1.子集问题，设n个元素没有先后关系，那么一共有 $2^n$ 个子集；2.排列问题，对所有n个元素进行全排列，共有 $n!$ 个排列
状态压缩：主要就是dp的一种状态，与dp转移关系不大
位运算：$a&(a-1)$ 把a的最后一个1去掉