Peter算法小课堂—经典线性DP问题(上）

本文章介绍一些经典DP问题，这些问题比较简单，常常出现在面试中。希望大家学完后能够熟练掌握DP的算法思想。

01背包

题目：给定n种物品和一个背包，第i个物品的体积为c[i]，价值为w[i]，背包的总容量为C。把物品装入背包时，第i件物品只有两种选择：装或不装。如何选择装入背包的物品，使装入背包的物品总价值最大

状态的设计

引入一个（N+1)*(C+1)的二维数组dp[][]，称为DP状态，dp[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值。然而最后的dp[N][C]就是问题的答案—把N个物品装入容量为C的背包里

DP转移方程

假设现在递推到dp[i][j]，分两种情况：

（1）第i个物品的体积比j大：不能装进背包中，dp[i][j]=dp[i-1][j]。

（2）第i个物品的体积比j小：分两种情况考虑

①装第i个物品：从前i-1个物品推广而来，前i-1件物品价值为dp[i-1][j]。第i件物品装入后，背包容量减少c[i]，价值增加w[i]，有dp[i][j]=dp[i-1][j-c[i]]+w[i]

②不装第i个物品：dp[i][j]=dp[i-1][j]

去两者中的最大值，状态转移方程变为：dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])

代码

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

再来个交替滚动数组

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

多重背包

题目：P1776 宝物筛选 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

我给出两种解法：①简单方法 ②二进制拆分优化

简单方法

转换成01背包，复杂度

状态转移方程：第i件物品分为装或者不装两种情况

dp[i][j]=max{dp[i-1][j],dp[i-1][j-k*c[i]]+k*w[i]}

1<=k<=min{m[i],j/c[i]}

代码

//滚动数组 多重背包（超时） 
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int n,C,dp[N];
int w[N],c[N],m[N];
int main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++) cin>>w[i]>>c[i]>>m[i];
	for(int i=1;i<=n;i++){
		for(int j=C;j>=c[i];j--){
			for(int k=1;k<=m[i]&&k*c[i]<=j;k++){
				dp[j]=max(dp[j],dp[j-k*c[i]]+k*w[i]);
			}
		}
	}
	cout<<dp[C];
	return 0;
}

二进制拆分优化

算法思路：这是一种很简单的优化方法，假设第i件物品mi=14，组合成15（0~14共15种）种情况。不过，要组成15种情况，其实不需要14件物品，因为任何一个正整数X，都能拆为若干2的倍数的和，如14=2+4+8，这样总复杂度就从变到

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int n,C,dp[N];
int w[N],c[N],m[N];
int new_n;
int new_w[N],new_c[N],new_m[N];
int main(){
	cin>>n>>C;
	for(int i=1;i<=n;i++) cin>>w[i]>>c[i]>>m[i];
	//二进制拆分
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m[i];j<<=1){
			m[i]-=j;
			new_c[++new_n]=j*c[i];
			new_w[new_n]=j*w[i];
		}
		if(m[i]){
			new_c[++new_n]=m[i]*c[i];
			new_w[new_n]=m[i]*w[i];
		}
	} 
	//01背包
	for(int i=1;i<=new_n;i++){
		for(int j=C;j>=new_c[i];j--){
			dp[j]=max(dp[j],dp[j-new_c[i]]+new_w[i]);
		}
	} 
	cout<<dp[C];
	return 0;
}

当然，以后还会学更快的算法，目前阶段就只要学习二进制拆分就好了

嗯嗯，后面的题我就挑难得讲一下转移方程来源，简单的就留给你们自己考虑，不会的问我偶

编辑距离

P2758 编辑距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

若word1[i]=word2[j]，则dp[i][j]=dp[i-1][j-1]

其他情况，dp[i][j]=min{dp[i-1][j-1],dp[i-1][j],dp[i][j-1]}+1（具体代码不给出，状态转移方程来源：思考两个字符串，用表格画出，分析即可得到 ）

最小划分

题目：724 · 最小划分 - LintCode

算法思路：最小划分问题可以转化成01背包问题。求出数组的和sum，把问题转换为：背包的容量为sum/2，把数组中的每个数看成物体的体积，求出背包里最多可以放多少res体积的物品？返回结果为|res-(sum-res)|

最优游戏策略

题目：Optimal Strategy for a Game | DP-31 - GeeksforGeeks 

有点难！定义二维数组dp，dp[i][j]表示从第i堆到第j堆硬币区间内，先手能拿到的最大值。

在硬币区间[i,j]内，先手有两种选择：

①拿i。接着对手也有两种选择：拿i+1，剩下[i+2,j]；拿j，剩下[i+1,j-1]

②拿j。接着对手也有两种选择：拿i，剩下[i+1,j-1]；拿j-1，剩下[i,j-2]。

得到的状态转移方程如下：

dp[i][j]=max{V[i]+min(dp[i+2][j],dp[i+1][j-1]),V[j]+min(dp[i+1][j-1],dp[i][j-2])}

dp[i][j]=V[i]   j=i

dp[i][j]=max(V[i],V[j])   j=i+1

今天先到这里了，下次课我们会细讲矩阵链乘法 子集和问题 LIS LCS

希望大家能关注、点赞、收藏哦，你的关注是我创作的动力φ(゜▽゜*)♪