文章目录
- 一、动态规划基础
- （1）线性DP
- 简介
- 步骤
- 例题
- 数字三角形--1536
- 破损的楼梯-3367
- 安全序列-3423
- （2）二维DP
- 简介
- 例题
- 摆花--389
- 选数异或--3711
- 数字三角形--505
- （3）最长公共子序列LCS
- LCS算法模型
- 最长公共子序列--1189
- 如何求出具体的子序列
- （4）最长上升子序列LIS
- LIS算法模型
- 例题
- 蓝桥勇士--2049
- 合唱队形--742
- 二、背包问题
- 01背包
- 01背包模型
- 小明的背包--1174
- 01背包的优化
- 背包与魔法--2223
- 完全背包
- 完全背包模型
- 小明的背包2--1175
- 多重背包
- 基础模型
- 小明的背包3--1176
- 二进制优化模型
- 新一的宝藏搜寻加强版--4059
- 单调队列优化多重背包
- 二维费用背包
- 小蓝的神秘行囊--3937
- 分组背包模型
- 小明的背包5-1178
- 三、树形DP
- 自下而上树形DP
- 最大独立集
- 自上而下树形DP
- 路径相关树形DP
- 树上路径1
- 树上路径2
- 换根DP
- 四、区间DP
- 石子合并--1233
- 涂色
- 制作回文串-1547
- 环形区间DP
- 能量珠-557
- 五、状压DP
- 六、数位DP
- 七、期望DP
一、动态规划基础
（1）线性DP
简介
- DP(动态规划)全称Dynamic Programming,是运筹学的一个分支，是一种将复杂问题分解成很多重叠的子问题，并通过子问题的解得到整个问题的解的算法。
- 在动态规划中有一些概念：状态：就是形如dp[i][j]=val的取值，其中i,j为下标，也是用于描述、确定状态所需的变量， val为状态值。
- 状态转移：状态与状态之间的转移关系，一般可以表示为一个数学表达式，转移方向决分迭代或递归方向。最终状态：也就是题目所求的状态，最后的答案。
步骤
例题
数字三角形–1536
1.为什么要用动态规划：
如果用贪心，每次选择最大的来走得到的结果不是正确答案。
2.这个三角形数组如何输入呢？
统计个数–N行有i个，用两层循环。
3.如何让一个点与下面的两个点进行比较？
利用i和j的关系。
- 分析
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=105;//开的数组
ll a[N][N],dp[N][N];//记录三角形和状态
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
//输入该三角形
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
cin>>a[i][j];
}
}
//从下往上进行更新
for(int i=n;i>=1;i--)
{
for(int j=1;j<=i;j++)
{
dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
}
}
cout<<dp[1][1]<<endl;//从下往上一直更新到第一个
return 0;
}
破损的楼梯-3367
- 分析：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;//开的数组
ll dp[N];//记录三角形和状态
const ll p=1e9+7;
bool broken[N];//桶--记录是否破损
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;cin>>n>>m;
//记录破损
for(int i=1;i<=m;i++)//破损的个数不止一个，所以用循环来写
{
int x;cin>>x;//创建桶
broken[x]=true;
}
dp[0]=1;//一开始就在0级台阶
if(!broken[1])dp[1]=1;//默认的第一节台阶为0
for(int i=2;i<=n;i++)
{
if(broken[i])continue;
dp[i]=(dp[i-1]+dp[i-2])%p;
}
cout<<dp[n]<<endl;
return 0;
}
- 总结：
注意状态的设置：这里的状态是方案数。
当从前往后进行更新的时候，注意先处理特殊，即0级台阶和一级台阶。
使用桶比0，1数组来记录破损的好处是什么？
使用桶来记录破损的好处是，它可以更高效地处理大量的破损情况。在这段代码中，如果使用0和1数组来记录破损，那么数组的大小将取决于输入的n值，这可能会导致内存不足的问题。而使用桶来记录破损，只需要一个大小为m的数组，其中m是破损的数量，这样可以减少内存的使用。此外，桶还可以方便地查找和更新破损的情况，提高了代码的效率。
安全序列-3423
-
分析：
1.我的想法：对于给定的题例来说：绑定两个00，当这两个0位于首尾两侧，分别有两种策略，位于中间有四种策略，最终还要去重。–难以计算
2.动态规划的思考思路：放一个桶的方案列出来，放两桶的方案列出来，观察规律，找到状态：以i结尾的方案数。
-
实现：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+9;
const ll p=1e9+7;
ll dp[N];
ll prefix[N];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,k;cin>>n>>k;
dp[0]=prefix[0]=1;//全部都不放也是一种状态，要初始化
//从前往后走
for(int i=1;i<=n;i++)
{
if((i-k-1)<1)dp[i]=1;//自己单独作为一个方案
else dp[i]=prefix[i-k-1];//否则就是以i结尾的前缀和
prefix[i]=(prefix[i-1] +dp[i])%p;//更新前缀和
}
cout<<prefix[n]<<endl;
//关于这里为什么不是dp[n]，这里的dp[n]表示的是以n结尾的方案数，而题目中要求的结果是从1
// 到n的方案数，所以用前缀和求和即可。
return 0;
}
（2）二维DP
简介
- 二维dp就是指dp数组的维度为二维的dp(当然有时候可能会三维，四维，或者存在一些优化使得它降维成一维)，广义的来讲就是有多个维度的dp,即用于描述dp状态的变量不止一个。
例题
摆花–389
- 分析：
- 实现：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=105;
const ll p=1e6+7;
ll a[N];
ll dp[N][N];//dp[i][j]表示到第i种花为止，到第j个位置为止，摆花的方案数
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
//状态转移之前先做初始化
dp[0][0]=1;//什么都不做也是有一种方案的
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)//从0开始是因为每一种花都要从前一种位置转移过来
{
for(int k=0;k<=a[i]&&k<=j;k++)
{
dp[i][j]=(dp[i][j]+dp[i-1][j-k])%p;//状态转移的公式
}
}
}
cout<<dp[n][m]<<endl;
return 0;
}
- 总结：
分析题干得到两个范围：不同种类的花的盆数，花放置的位置。所以采用二维DP。
状态转移之前一定不要忘了初始化。
状态转移的公式是怎么得出的呢？
先要画出所有的方案，用题中变量i和j表示，可以看出最后放置的都是i这种花，则它的上一种状态是第i-1种花，剩下j-k个位置。
还要留意变量的范围。
选数异或–3711
- 分析：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
const ll p= 998244353;
ll a[N];
ll dp[N][70];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,x;cin>>n>>x;
for(int i=1;i<=n;i++)cin>>a[i];
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<64;j++)
{
dp[i][j]=(dp[i-1][j]+dp[i-1][j^a[i]])%p;
}
}
cout<<dp[n][x];
return 0;
}
- 总结：
解题的关键就是确定转化方程。
数字三角形–505
- 分析：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=150;
const ll p= 998244353;
ll a[N][N];
ll dp[N][N][N];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
//三角形输入一下
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
cin>>a[i][j];
}
}
//开始转化
for(int i=n;i>=1;i--)
{
for(int j=1;j<=i;j++)
{
for(int k=0;k<=n-i;k++)
{
if(k>=1)dp[i][j][k]=a[i][j]+max(dp[i+1][j][k],dp[i+1][j+1][k-1]);
else dp[i][j][k]=a[i][j]+dp[i+1][j][k];
}
}
}
//判断奇偶性
if(n&1)cout<<dp[1][1][(n-1)/2];//是偶数
else cout<<max(dp[1][1][(n-1)/2],dp[1][1][n-1-(n-1)/2]);
return 0;
}
- 总结：
- 增加了一个新的变量–k次右移。
- 最后为什么要进行奇偶性的判断呢？
这段代码在最后判断奇偶性是为了处理一个特殊情况。根据代码的逻辑，它计算了一个三角形的路径和的最大值。然而，当输入的三角形行数为偶数时，存在两种可能的最大路径和，因为可以选择中间的两个节点之一作为起点。
为了解决这个问题，代码通过判断输入的行数是否为偶数来确定要选择哪个最大路径和。如果行数是奇数，则直接输出dp[1][1][(n-1)/2]作为结果；如果行数是偶数，则比较dp[1][1][(n-1)/2]和dp[1][1][n-1-(n-1)/2]这两个值，并输出其中较大的那个作为结果。
这样做的原因是，对于偶数行的三角形，有两种可能的最大路径和，而代码需要确定哪种路径和更大。
（3）最长公共子序列LCS
LCS算法模型
- 转化过程：
- 分析过程：
最长公共子序列–1189
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+9;
int a[N],b[N],dp[N][N];
int main()
{
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
//默认初始化为DP[0][0]=0
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
cout<<dp[n][m]<<endl;
return 0;
}
如何求出具体的子序列
- 分析：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+9;
int a[N],b[N],dp[N][N];
int main()
{
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
//默认初始化为DP[0][0]=0
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
vector<int>v;
int x=n,y=m;
while(x&&y)//如果跳出地图，认为结束
{
if(a[x]==b[y])//相等的情况，往左上角走
{
v.push_back(a[x]);//找到了一个公共元素
x--;y--;//到左上角去了
}
else if(dp[x-1][y]>dp[x][y-1])//上面的更小，往 左边走
x--;
else y--;
}
reverse(v.begin(),v.end());//求出来的是反向的，所以倒置一下
for(const auto &i:v)cout<<i<<' ';
return 0;
}
- 运行结果：
（4）最长上升子序列LIS
LIS算法模型
- 分析：
例题
蓝桥勇士–2049
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+9;
int a[N],dp[N];//这里的dp[i]是1~i的最长上升子序列的长度
//模板题：求最长上升子序列的元素数
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
{
dp[i]=1;
for(int j=1;j<i;j++)//用来检查a[i]之前的元素
{
if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);
}
}
//最后输出的时候不能输出dp[n]（以n结尾），而是要输出dp[1~n]
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
cout<<ans<<endl;
return 0;
}
合唱队形–742
- 想法：枚举最高点。找到左边的最长上升子序列+右边的反向最长上升子序列。
#include<bits/stdc++.h>
using namespace std;
const int N=101;
int a[N],dp[N],dpr[N];//这里的dp[i]是1~i的最长上升子序列的长度
//模板题：求最长上升子序列的元素数
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
//正向的上升子序列的长度
for(int i=1;i<=n;i++)
{
dp[i]=1;
for(int j=1;j<i;j++)
{
if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);
}
}
//反向的上升子序列的长度
for(int i=n;i>=1;i--)
{
dpr[i]=1;
for(int j=i+1;j<=n;j++)//注意这里j的范围，是从最右边开始的
{
if(a[i]>a[j])dpr[i]=max(dpr[i],dpr[j]+1);
}
}
int ans=n;//假设一个最大值，一开始要请出n位同学
for(int i=1;i<=n;i++)ans=min(ans,n-(dp[i]+dpr[i]-1));//最小值：总的同学数量-留下来的同学数量
cout<<ans<<endl;
return 0;
}
二、背包问题
01背包
01背包模型
- 状态：到第i个物品为止，当前体积下的最大价值。
小明的背包–1174
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=102;
const int M=1010;
ll dp[N][M];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,V;cin>>n>>V;
ll w,v;
for(int i=1;i<=n;i++)
{
cin>>w>>v;
for(int j=0;j<=V;j++)
{
if(j>=w)dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);//这里增加条件是为了防止越界
else dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][V]<<endl;
return 0;
}
01背包的优化
- 分析：
- 优化上述问题–小明的背包
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=102;
const int M=1010;
ll dp[M];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,V;cin>>n>>V;
ll w,v;
for(int i=1;i<=n;i++)
{
cin>>w>>v;
for(int j=V;j>=w;j--)//注意这里j的范围
{
dp[j]=max(dp[j],dp[j-w]+v);
}
}
cout<<dp[V]<<endl;
return 0;
}
背包与魔法–2223
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e4+9;
ll dp[N][2];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m,k;cin>>n>>m>>k;
//遍历每一个物品
for(int i=1;i<=n;i++)
{
ll w,v;
cin>>w>>v;
for(int j=m;j>=0;j--)
{
if(j>=w)
{
dp[j][0]=max(dp[j][0],dp[j-w][0]+v);//不选
dp[j][1]=max(dp[j][1],dp[j-w][1]+v);//选但不用魔法
}
if(j>=w+k)
{
dp[j][1]=max(dp[j][1],dp[j-w-k][0]+2*v);//选且用魔法
}
}
}
cout<<max(dp[m][0],dp[m][1])<<endl;
return 0;
}
完全背包
完全背包模型
- 完全背包也叫无穷背包，即每种物品有无数个的背包。
- 有一个体积为V的背包，商店有个物品，每个物品有一个价值v和体积w,每个物品有无限多个，可以被拿无穷次，问能够装下物品的最大价值。
这里每一种物品只有无穷种状态即“拿0个、1个、2个…无穷多个”。 - 设状态dp[i]表示拿的物品总体积为j的情况下的最大价值。我们并不关心某个物品拿了几个，只关心当前体积下的最大价值。
- 转移方程为：dp[i]=max(dp[i],dp[i-w]+v),现在就必须使用“新数据”来更新“新数据”，因为新数据中包括了拿当前这个物品的状态，而当前这个物品是可以被拿无数次的。最后输出dp[V]即可。
小明的背包2–1175
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+9;
int dp[N];
int main()
{
int n,m;cin>>n>>m;
//从前往后枚举物品，t表示第几个物品
for(int t=1;t<=n;++t)
{
int w,v;cin>>w>>v;
for(int i=w;i<=m;++i)//体积
{
dp[i]=max(dp[i],dp[i-w]+v);
}
}
cout<<dp[m];
return 0;
}
多重背包
基础模型
- 有一个体积为V的背包，商店有种物品，每种物品有一个价值v和体积w,每种物品有s个，问能够装下物品的最大价值。这里每一种物品只有s+1种状态.
即“拿0个、1个、2个…s个”。在基础版模型中，多重背包就是将每种物品的s个摊开，变为s种相同的物品，从而退化成01背包处理。 - 只需要在01背包的基础上稍加改动，对每一个物品循环更新s次即可。
- 时间复杂度为O（NVS）。
小明的背包3–1176
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int dp[N];
int main()
{
int n,m;cin>>n>>m;
//倒着更新
for(int t=1;t<=n;++t)
{
int w,v,s;cin>>w>>v>>s;
while(s--)
{
for(int j=m;j>=w;j--)
{
dp[j]=max(dp[j],dp[j-w]+v);
}
}
}
cout<<dp[m];
return 0;
}
二进制优化模型
- 多重背包基础模型的时间复杂度为O(nsv),当s较大时，容易超时。
- 为了解决这个问题，我们可以在“拆分”操作时进行一些优化，我们不再是拆分成均为1个物品的组，而是每一组的物品个数为1、2、4、8·，最后剩下的单独为一组，这样一定存在一种方案来表示0~s的所有情况（想象二进制数的表示方法）。
- 在经典模型中，一种物品将被拆分为s组，每组一个，而二进制优化模型中，一种物品将被拆分为约1og2(s)组，其中每组个数为1、2、4、8·，例如s=11,将被拆为s=1+2+4+4。
- 这样对拆分后的物品跑一遍01背包即可，时间复杂度为O(n*1og(s)*V)。
新一的宝藏搜寻加强版–4059
S=14=1+2+4+7。跑四次01背包。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e4+5;
ll dp[N];
int main()
{
ios::sync_with_stdio, cin.tie(0), cout.tie(0);
ll n, V; cin >> n >> V;
for (int i = 1; i <= n; i++)
{
ll v, w, s; cin >> v >> w >> s;
for (int k = 1; k <= s; s -= k, k += k)//相当于加数 ，k+=k是k翻倍
{
for (int j = V; j >= k*v; j--)//跑01背包
{
dp[j] = max(dp[j], dp[j - k*v] + k*w);
}
}
for(int j=V;j>=s*v;j--)//s有可能剩下
{
dp[j]=max(dp[j],dp[j-s*v]+s*w);
}
}
cout << dp[V]<<endl;
return 0;
}
单调队列优化多重背包
这里附上一位大佬的内容补充
二维费用背包
- 有一个体积为V的背包，商店有种物品，每种物品有一个价值v、体积w、重量m,每种物品仅有1个，问能够装下物品的最大价值。
这里每一种物品只有2种状态即“拿0个、1个”，但是需要同时考虑体积和重量的限制。 - 只需要在01背包的基础上稍加改动，将状态转移方程修改为二维的即可，同样是倒着更新。
- dp[i]表示当前体积为i,重量为j的情况下所能拿的物品的最大价值。状态转移方程为dp[i][j]=max(dp[i[j],dp[i-w][j-m]+v);
小蓝的神秘行囊–3937
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N =105;
ll dp[N][N];
int main()
{
int n,V,M;cin>>n>>V>>M;
//枚举每一个物品
for(int i=1;i<=n;i++)
{
int v,m,w;cin>>v>>m>>w;
for(int j=V;j>=v;j--)
{
for(int k=M;k>=m;k--)
{
dp[j][k]=max(dp[j][k],dp[j-v][k-m]+w);
}
}
}
cout<<dp[V][M]<<'\n';
return 0;
}
分组背包模型
- 有一个体积为V的背包，商店有组物品，每组物品有若干个价值v、体积w,每组物品中至多选1个，问能够装下物品的最大价值。
- 前面已经见过这么多背包了，在这里就直接给出分组背包的定义。设状态dp[i][j]表示到第i组，体积为j的最大价值，在这里不能忽略第一维，否则可能导致状态转移错误！
状态转移方程为：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);
小明的背包5-1178
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N =105;
ll dp[N][N];
int main()
{
int n,V;cin>>n>>V;
//枚举每一个物品
for(int i=1;i<=n;i++)
{
int s;cin>>s;
for(int j=0;j<=V;j++)dp[i][j]=dp[i-1][j];//这一组中一个都不拿的最大价值
while(s--)
{
ll w,v;cin>>w>>v;
for(int j=w;j<=V;j++)dp[i][j]=max(dp[i][j],dp[i-1][j-w]+v) ;
}
}
cout<<dp[n][V]<<'\n';
return 0;
}
三、树形DP
自下而上树形DP
最大独立集
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N =1e5;
int n,a[N];
ll dp[N][2];
vector<int>e[N];
void dfs(int u)
{
for(auto v:e[u])
{
dfs(v);
dp[u][1]+=dp[v][0];//选择了节点u
dp[u][0]+=max(dp[v][0],dp[v][1]);//没有选择节点u，那么节点v可以选择也可以不选择
}
dp[u][1]+=a[u];//选择了节点u，增加节点u的快乐指数
}
int main()
{
cin>>n;
set<int>st;//存放可能是根结点的值的编号
for(int i=1;i<=n;i++)cin>>a[i],st.insert(i);//输入每一个员工的快乐指数
for(int i=1,x,y;i<n;i++)
{
cin>>x>>y;
e[y].push_back(x);//y是x的直接父节点
st.erase(x);
}
int rt=*st.begin();//只剩下根结点
dfs(rt);
cout<<max(dp[rt][0],dp[rt][1]);
return 0;
}
自上而下树形DP
- 考虑dp,通常树形dp状态设定
- 一维表示当前子树，但这里题目要求儿子结点和自己不能同时选择，函此对王每个结点，选不选择影响着儿子节点，所以多开一维记录选没选。分类处理一下即可。
- 形式化一点来讲，设f[i][0]表示当前点不选的最大值，f[i][1]表示当前点选了的最大值。
- 例题1：
#include<bits/stdc++.h>
using namespace std;
#define maxn 110000
int n,val[maxn];
struct Edge{
int nex,to;
}edge[maxn<<1];
int head[maxn],cnt;
int f[maxn][2];
void add(int from,int to)//建树
{
edge[++cnt].nex=head[from];
head[from]=cnt;
edge[cnt].to=to;
return ;
}
void dfs(int u,int fa)
{
for(int i=head[u];i;i=edge[i].nex)//遍历u这个节点的儿子
{
int v=edge[i].to;
if(v!=fa)continue;//点是父亲就不处理
dfs(v,u);//尽可能往叶子结点去递推
//代表v这个儿子的状态已经被处理好
f[u][0]+=max(f[v][0],f[v][1]);//代表u这个点不选，那么v可选可不选
f[u][1]+=f[v][0]; //代表u这个点已选，那么v只能不选
}
return ;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>val[i];//读入n个点的权值
f[i][1]=val[i];//做初始化
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
add(u,v);add(v,u);
}
dfs(1,0);
cout<<max(f[1][0],f[1][1]);
return 0;
}
- 例题2：
·设f[u][v]表示u这颗子树用了v体积且选了u这个点的最大价值。
·枚举子树，进行合并转移即可。
·时间复杂度0(n^3)。
#include<bits/stdc++.h>
using namespace std;
#define maxn 110000
int n,V;
struct Edge{
int nex,to;
}edge[maxn<<1]; // 存储边的信息
int head[maxn],cnt; // 存储每个节点的第一条边的索引
int f[maxn][maxn]; // 动态规划的状态数组
int w[maxn],v[maxn]; // 存储每个节点的权重和体积
vector<int>g[maxn]; // 存储每个节点的子节点
void add(int from,int to)//建树
{
edge[++cnt].nex=head[from];
head[from]=cnt;
edge[cnt].to=to;
return ;
}
void dfs(int u,int fa)
{
memset(f[u],-0x3f,sizeof(f[u]));//初始化
//把当前节点u的儿子对应的子树看做物品，进行01背包转移
if(v[u]<V)f[u][v[u]]=w[u];//u这个节点为根对应的子树里只有u这一个结点
for(int i=head[u];i;i=edge[i].nex)
{
int v=edge[i].to;
if(v==fa)continue;
dfs(v,u);
//当前子树的背包过程
vector<int>nf(f[u],f[u]+V+1);
for(int v1=0;v1<=V;v1++)
{
for(int v2=0;v1+v2<=V;v2++)
{
nf[v1+v2]=max(nf[v1+v2],f[u][v1]+f[v][v2]);
}
}
for(int v=0;v<V;v++)f[u][v]=nf[v];
}
return ;
}
int main()
{
cin>>n>>V;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
add(u,v);add(v,u);
}
dfs(1,0);
int ans=0;
for(int i=0;i<V;i++)ans=max(ans,f[1][i]);
cout<<max(f[1][0],f[1][1]);
return 0;
}
- 算法分析：以dp来决定。
- 总结：
- 简单来讲，就是当前节点和儿子结点之间有限制关系，那么为了解决这个问题，我们多开一维记录当前节点选的状态即可。
- 树上背包的trick很常见，掌握十分必要。
路径相关树形DP
树上路径1
- 第一种思路：
- 第二种思路：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
ll dp[N];
int n,m,k;
int dep[N]={1},f[N];
vector<int> e[N], t; // 定义e为邻接表，t为临时向量
vector<pair<vector<int>, ll>> w[N]; // 定义w为每个节点的路径和权值对的向量
//搜索
void dfs(int u)
{
for(auto v:e[u])//遍历每一个节点，选择在u上任何一条路径的dp值
{
dfs(v);
dp[u]+=dp[v];//直接把子节点的dp值相加
}
for(auto &t:w[u])
{
ll sum=dp[u];
for(auto nw:t.first)
{
sum-=dp[nw];//把路径上的点的dp值都减1
for(auto v:e[nw])sum+=dp[v];//把这条路径上所有点的子节点的dp值都加入到结果里
}
dp[u]=max(dp[u],sum+=t.second);
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;//读入n个点，m条边
for(int i=2;i<=n;i++)
{
cin>>f[i];//对于2~n的每一个节点，读入该节点的父节点
e[f[i]].push_back(i);
dep[i]=dep[f[i]];//求出每一个节点的深度，该节点的深度等于该节点的父节点+1
}
for(int i=1,x,y;i<=m;i++)
{
ll val;
cin>>x>>y>>val;//输入路径的两个端点和路径的权值
t.clear();
while(x!=y)//把x到y的每一个节点装入vector里
{
if(dep[x]>dep[y])t.push_back(x),x=f[x];
else t.push_back(y),y=f[y];
}
t.push_back(x);//此时x是该路径上深度最浅的节点
w[x].push_back({t,val});//把该路径的vector和权值都记录在x上
}
dfs(1);
cout<<dp[1];
return 0;
}
树上路径2
- 与上一道题不同的是改成考虑最低点是否被选择。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N =1e5+9;
vector<int> e[N]; // 邻接表
vector<pair<int, ll>> w[N]; // 边的权值
ll dp[N][N]; // 动态规划数组
int dep[N]; // 节点深度
int n, m; // 节点数和边数
//搜索
void dfs(int u)
{
ll sum=0;
for(int i=1;i<=dep[u];i++)dp[u][i]=1e18; //初始化dp数组，全部初始化为最大值
for(auto v:e[u])//遍历每一个节点
{
dfs(v);
sum+=dp[v][dep[u]+1];
if(sum>=1e18)
{
cout<<-1;//存在u的子节点v不能被完全覆盖
exit(0);//退出
}
for(int i=1;i<=dep[u];i++)
dp[u][i]=min(dp[u][i],dp[v][i]-dp[v][dep[u]+1]);
}
for(int i=1;i<=dep[u];i++)dp[u][i]+=sum;//不选择u为最深的最小代价
for(auto v:w[u])
{
dp[u][dep[v.first]]=min(dp[u][dep[v.first]],sum+=v.second);
}
for(int i=2;i<=dep[u];i++)dp[u][i]=min(dp[u][i],dp[u][i-1]);//优化
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;//读入n个点，m条边
for(int i=2;i<=n;i++)
{
int f;
cin>>f;
e[f].push_back(i);
dep[i]=dep[f]+1;
}
for(int i=1;i<=m;i++)
{
int x,y;
ll val;
cin>>x>>y>>val;
if(dep[x]>dep[y]) swap(x,y);//此时x是两者中深度较小的那一个
w[y].push_back({x,val});//把x和被选择的代价记录在y上
}
dfs(1);
cout<<dp[1][1];
return 0;
}
换根DP
- 换根DP,又叫二次扫描，是树形DP的一种。
- 具有以下特点：以树上的不同点作为根，其解不同，无法通过一次搜索完成答案的求解，因为一次搜索只能得到一个节点的答案。
- 题目描述大致如：一棵树…求以哪一个节点为根的时候，xxx最大/最小.…
先以树形DP的形式求出以某一个点为根的时候的答案（一般都是以1为根的时候)，然后再进行一次自上而下的DFS计算答案。
也就是说，分两步:
1.树形DP
2.在进行第二次DFS时，两个点之间的关系。
- 例题：
给定一个个点的无根树，问以树上哪个节点为根时，其所有节点的深度和最大？深度：节点到根的简单路径上边的数量 n<=le5
代码：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n;
#define maxn 110000
ll sum,ans[maxn],siz[maxn],f[maxn];
vector<int>v[maxn];
void dfs(int u,int dep,int fa)
{
sum+=dep;
for(int i=0;i<v[u].size();i++)
{
int to=v[u][i];
if(to==fa)continue;
dfs(to,dep+1,u);
siz[u] +=siz[to];
}
return ;
}
void dfs1(int u,int fa)
{
for(int i=0;i<v[u].size();i++)
{
int to=v[u][i];
if(to==fa)continue;
ans[to]=ans[u]=siz[to]+(n-siz[to]);
dfs1(to,u);//向下递归去更改其他的值
}
return ;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)siz[i]=1;//初始化
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
sum=0;
dfs(1,0,0);
f[1]=sum;
dfs1(1,0);
ll ans=0;
for(int i=1;i<=n;i++)
{
ans+=max(ans,f[i]);
}
cout<<ans<<endl;
return 0;
}
- 总结：
- 如果我们假设某个节点为根，将无根树化为有根树，在搜索回溯时统计子树的深度和，则可以用一次搜索算出以该节点为根时的深度和，其时间复杂度为O(n)·如果我们每个点都这么求，则O(n^2).
- 例题2：
题目大意：给定一棵个点的无根树，点带权，边带权，求一个点，使得其他点到这个点的距离和最小。距离：a->b的距离为a的点权乘以a>b的路径长度
#include<bits/stdc++.h> // 引入C++标准库
using namespace std; // 使用C++标准命名空间
using ll=long long; // 定义长整型别名ll
#define maxn 110000 // 定义最大节点数为110000
int n,c[maxn],dist[maxn]; // 定义全局变量n, c数组， dist数组
struct Edge{ // 定义边的结构体
int nex,to,dis; // 定义边的下一个节点、目标节点和距离
}edge[maxn<<1]; // 定义边的数组，大小为2倍的最大节点数
int siz[maxn],head[maxn],cnt,tot; // 定义全局变量siz数组， head数组， 计数器cnt, 总和tot
void add(int from,int to,int dis) // 添加边的函数
{
edge[++cnt]={head[from],to,dis}; // 将新边添加到边的数组中
head[from]=cnt; // 更新头节点的指针
return ;
}
int sum[maxn]; // 定义全局变量sum数组
ll f[maxn]; // 定义全局变量f数组
void dfs(int x,int fa) // 深度优先搜索函数
{
siz[x]=1;sum[x]=c[x]; // 初始化当前节点的大小和总和
for(int i=head[x];i;i=edge[i].nex) // 遍历当前节点的所有邻接节点
{
int v=edge[i].to; // 获取邻接节点
if(v==fa)continue; // 如果邻接节点是父节点，则跳过
dist[v]=dist[x]+edge[i].dis; // 计算路径长度
dfs(v,x); // 递归调用深度优先搜索函数
siz[x]+=siz[v]; // 更新当前节点的大小
sum[x]+=sum[v]; // 更新当前节点的总和
}
return ;
}
void dfs1(int x,int fa) // 深度优先搜索函数1
{
for(int i=head[x];i;i=edge[i].nex) // 遍历当前节点的所有邻接节点
{
int v=edge[i].to; // 获取邻接节点
if(v==fa)continue; // 如果邻接节点是父节点，则跳过
f[v]=f[x]-sum[v]*edge[i].dis+(tot-sum[v])*edge[i].dis; // 更新f数组的值
dfs1(v,x); // 递归调用深度优先搜索函数1
}
return ;
}
int main() // 主函数
{
cin>>n; // 输入节点数
for(int i=1;i<=n;i++)c[i]=1,tot+=c[i]; // 初始化c数组和总和tot
for(int i=1;i<n;i++) // 输入边的信息
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c); // 添加边
add(b,a,c); // 添加边
}
dfs(1,0); // 从节点1开始深度优先搜索
for(int i=1;i<=n;i++) // 更新f数组的值
{
f[1]+=dist[i]*c[i];
}
dfs1(1,0); // 从节点1开始深度优先搜索1
ll ans=10100101000; // 定义答案ans
for(int i=1;i<=n;i++) // 遍历所有节点，找到最小的f值
{
ans=min(ans,f[i]);
}
cout<<ans<<endl; // 输出答案
return 0;
}
- 总结：
- 由此我们可以看出换根DP的套路：
1,指定某个节点为根节点
2,第一次搜索完成预处理(如子树大小等)，同时得到该节点的解。
3,第二次搜索进行换根的动态规划，由已知解的节点推出相连节点的解。
四、区间DP
区间DP是以区间为尺度的DP,一般有以下特点：
可以将一个大区间的问题拆成若干个子区间合并的问题
两个连续的子区间可以进行整合、合并成一个大区间
石子合并–1233
- 每次只能合并相邻的两堆石子
- 那么如果现在想要将区间[l,r]的所有石子合并为一堆，那么一定是将[L,r]中的两堆石子合并成整个区间[l，r]。可以考虑区间DP
- 纠正一个误区：
#include <bits/stdc++.h>
using namespace std;
const int N=210;
int dp[N][N];//dp[i][j] 表示 区间 (i,j) 合并区间的最小花费
int sum[N]; //求前缀和的
int main()
{
int n;cin>>n;
memset(dp,0x3f,sizeof(dp)); //初始化为最大值 因为要求最小花费
for(int i=1;i<=n;i++){
cin>>sum[i];//输入石子的数量
dp[i][i]=0; //初始化区间 (i,i) 就是合并自己这一堆的最小花费
sum[i]+=sum[i-1];//求前缀和
}
for(int len=2;len<=n;len++){ //这个是遍历区间长度
for(int l = 1 ; l <= n - len +1; l++){//细节问题不能忽视 当 n=4 len=2 的时候 maxl=3 maxr=4 是符合区间长度为2的要求的
int r = l + len -1;//这个是右端点的位置
for(int k = l ; k < r ; k++){//这个是枚举区间的中间值(i,j)=>(i,k)+(k+1,j)
dp[l][r] = min(dp[l][r] , dp[l][k] + dp[k+1][r] + sum[r]-sum[l-1]);
//合并区间内的花费 最小值 可以从 区间(i,k) 和 区间(k+1,j)两个合并的来
}
}
}
cout<<dp[1][n]; //表示合并区间(1,n)的最小花费
return 0;
}
涂色
- 端点颜色相同：
- 端点颜色不同：
#include<bits/stdc++.h>
using namespace std;
const int N=1e8;
int dp[60][60];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
string s;
cin>>s;
int n=s.size();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dp[i][j]=N;
for(int i=0;i<n;i++)
dp[i][i]=1;
for(int len=2;len<=n;len++)
for(int i=0;i<=n-len;i++)
{
int j=i+len-1;
if(s[i]==s[j]) dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
else
{
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
cout<<dp[0][n-1];
return 0;
}
制作回文串-1547
- 分析：
- 转移方程：
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+9;
int dp[N][N];
main()
{
string s;
int n,m,w1[30],w2[30];cin>>m>>n>>s;
for(int i=1;i<=m;i++)
{
char ch;cin>>ch;
cin>>w1[ch-'a']>>w2[ch-'a'];
for(int len=2;len<=n;len++)
{
for(int i=0;i+len-1<n;i++)
{
int j=i+len-1;
if(s[i]==s[j])
{
if(len==2)
dp[i][j]=0;
else dp[i][j]=dp[i+1][j-1];
}
else
{
dp[i][j]=min(dp[i+1][j]+min(w1[s[i]-'a'],w2[s[i]-'a']),dp[i][j-1]+min(w1[s[j]-'a'],w2[s[j]-'a']));
}
}
}
}
cout<<dp[0][n-1]<<endl;
return 0;
}
环形区间DP
- 环形区间DP与普通区间DP的区别只在于环形区间DP的区间是首尾相连的环形。
- 要点：
- 数据的处理方法是将原区间复制一份在后边，总长度×2。
- 枚举的方法与普通区间DP一致。
- 统计答案时要枚举所有的答案区间，找出最优答案。
能量珠-557
//这是一道环形区间dp的模板题
//环形dp与普通dp的区别：
//将原区间复制一份，长度变成二倍，注意枚举右端点时可以达到2N，其余与普通dp相同
#include <bits/stdc++.h>
using namespace std;
const int maxn=200;
int dp[2*maxn][2*maxn];//dp[i][j]表示将区间[i,j]的珠子聚合之后释放的最大能量
int value[maxn*2];//存储每个珠子的头标记，由于珠子呈环形，故取二倍长度
int main()
{
int N;
cin>>N;
for(int i=1;i<=N;i++)
{
cin>>value[i];//输入每个珠子的头标记
value[i+N]=value[i];//由于是环形dp，将原序列复制一份，长度变成二倍
}
for(int len=2;len<=N;len++)//枚举所有可能的区间长度2~N
{
for(int i=1;i+len-1<=2*N;i++)//枚举所有可能的左端点i，注意右端点可以到2N
{
int j=i+len-1;//计算对应的右端点j
for(int k=i;k<j;k++)//枚举[i,j]内所有可能的分割点k
{
//先将[i,k]的珠子合并，能量为dp[i][k],
//再将[k+1,j]的珠子合并，能量为dp[k+1][j]
//最后将这两颗珠子合并,
//能量为第i个珠子的头标记、第k个珠子的尾标记(第k+1个珠子的头标记)、第j个珠子的尾标记(第j+1个珠子的头标记)三者相乘
//即value[i]*value[k+1]*value[j+1]
//三者相加，不断比较出最大值更新dp[i][j]即可
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+value[i]*value[k+1]*value[j+1]);
}
}
}
//由于本题没有指定第一个珠子的编号，因此每个珠子都可以作为第一个珠子
//故需要遍历所有的珠子，将其作为第一个珠子，然后比较出最大的合并能量
int ans=0;
for(int i=1;i<=N;i++)
{
ans=max(ans,dp[i][i+N-1]);
}
cout<<ans<<endl;
return 0;
}
五、状压DP
- 状态压缩：状态压缩就是使用某种方法来表示某种状悉，通常是用一多01数字二进制数)来表示各个状态。这就要求使用状态压缩的对象的状态必须只有两种，0或1；当然如果有三种状态用三进制来表示也未尝不可。
- 题目特征：解法需要保存一定的状态数据表示一种状态的一个数据值)，每个状态数据通常情况下是可以通过2进制来表示的。这就要求状态数据的每个单元只有两种状态，这样用0或者1来表示状态数据的每个单元。
#include<bits/stdc++.h>
using namespace std;
#define maxn 2100000
int n,m,a[maxn],f[maxn],k;//k是糖果包里的个数
int main()
{
cin>>n>>m>>k;//输入糖果包数量n，糖果种类m和每个糖果包中的糖果数量k
int maxx=(1<<m)-1;//计算所有口味组合的最大值
for(int i=0;i<maxn;i++)f[i]=0x3f3f3f3f;//初始化f数组为最大值
for(int i=0;i<n;i++)
{
int x;
for(int j=0;j<k;j++)
{
cin>>x;//输入第i个糖果包中的第j个糖果的口味
a[i]=a[i]|(1<<(x-1));//将第i个糖果包的口味压缩为一个整数a[i]
}
f[a[i]]=1;//将f[a[i]]设为1，表示已经有一个糖果包包含了这个口味组合
}
f[0]=0;//将f[0]设为0，表示没有口味组合的情况不需要任何糖果包
//状态转移
//枚举每一个糖果包，枚举每一个状态
for(int i=0;i<n;i++)
{
for(int j=1;j<=maxx;j++)
{
f[j|a[i]]=min(f[j|a[i]],f[j]+1);//更新f[j|a[i]]的值，表示包含当前糖果包的情况下，达到口味组合j所需的最少糖果包数量
}
}
cout<<f[(1<<m)-1]<<endl;//输出达到所有口味组合所需的最少糖果包数量
return 0;
}
六、数位DP
- 数位DP往往都是这样的题型，给定一个闭区间[l,r]，让你求这个区间中满足某种条件的数的总数。
- 所谓数位dp,就是对数位进行dp,也就是个位、十位等。
- 通过记忆化搜索来优化。
- 最常用的枚举方式是控制上界枚举。
- 控制上界枚举就是要让正在枚举的这个数不能超过上界。
- 我们常常利用一个bool变量limit来表明该数位前的其他数位是否恰好都处于最大状态。如果目前这个数不是这个位置最大的数字，那么可取的范围为0-9，否则范围将被限制在该数位在上界中的最大值。
- 注意，前导零要根据题目特殊处理。
- 例题：
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#define maxn 2100000
ll a,b,dig[20],cnt;
ll f[20][20];//表示长度为i的数字，最高位为j的windy数数量
ll solve(ll x)
{
memset(dig,0,sizeof(dig));
cnt=0;
while(x)
{
dig[++cnt]=x%10;
x/10;
}//基本的拆分数字 123->1 2 3
//要求长度<=cnt的windy
ll ans=0;
for(int i=1;i<cnt;i++)
{
for(int j=1;j<=9;j++)
{
ans+=f[i][j];
}
}//表示长度小于等于有边界长度的数字
//长度跟我们右边界x长度一样的
for(int i=1;i<dig[cnt];i++)
{
ans+=f[cnt][i];
}
//逐位处理
for(int i=cnt-1;i>=1;i--)//枚举当前是哪一位
{
for(int j=0;j<=dig[i]-1;j++)//当前位数的最高位填的是什么
{
if(abs(j-dig[i+1])>=2)ans+=f[i][j];
}//我们要填的那个数字次高位小于右边界的次高位 ，那么我们后面随便填
if(abs(dig[i+1]-dig[i])<2)break;
}
return ans;
}
int main()
{
cin>>a>>b;
for(int i=0;i<=9;i++)f[i][i]=1;
for(int i=1;i<=10;i++)//枚举当前数字的位数
{
for(int j=0;j<=9;j++)//当前位数的最高位填的是什么
{
for(int k=0;k<=9;k++)//
{
if(abs(j-k)>=2)f[i][j]+=f[i-1][k];
}
}
}
cout<<solve(b)-solve(a-1);
return 0;
}
七、期望DP
- 期望：
- 期望的性质：
- 全期望公式：
- 对于一些比较难找到递推关系的数学期望问题，可以利用期望的定义式，根据实际情况以概率或者方案数（也就是概率*总方案数）作为一种状态，将问题变成比较一般的统计方案数问题或者利用全概率公式计算概率的递推问题。
- 一般来说，概率DP找到正确的状态定义后，转移是比较容易想到的。但状态一定是“可数的，把有范围的整数作为数组下标。事实上，将问题直接作为状态是最好的。如问“人做X事的期望次数”，则设计状态为f[i]表示个人做完事的期望
- 常见设转移方程数组的方法：
- F[I]表示的是由状态变成最终状态的期望或按照题意直接设。
- 例题：
#include<bits/stdc++.h>
using namespace std;
#define maxn 1100000
double f[maxn];
int n,k;
int main()
{
cin>>n>>k;
f[1]=1;
for(int i=2;i<=n;i++)
{
f[i]=f[i-1]+(k-f[i-1])/k;//相当于全概率公式
}
cout<<fixed<<setprecision(6)<<f[n]<<endl;
return 0;
}
如果你想要控制它输出为6位小数，你可以使用C++的iomanip库中的setprecision函数。这个函数可以设置输出的精度。
包含iomanip库。
使用setprecision函数设置输出的精度为6。
- 如果要买一种新的，需要买多少张？
#include<bits/stdc++.h>
using namespace std;
#define maxn 1100000
double f[maxn];
int n,k;
int main()
{
cin>>n>>k;
f[1]=1;
for(int i=2;i<=k;i++)
{
f[i]=f[i-1]+(double)k/(double)(k-i+1);//相当于全概率公式
}
cout<<fixed<<setprecision(6)<<f[n]<<endl;
return 0;
}
- 总结：
- 例题：
#include<bits/stdc++.h>
using namespace std;
#define maxn 1100000
int f[maxn],p[maxn];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;cin>>t;
int cnt;
while(t--)
{
memset(f,0,sizeof f);
memset(p,0,sizeof p);
cnt++;
int n,k,m;
cin>>n>>k>>m;
for(int i=0;i<n;i++)//读入概率
cin>>p[i];
f[1]=p[0];//初始化
for(int i=2;i<=m;i++)
{
for(int j=0;j<n;j++)
{
f[i]+=pow(f[i-1],j)*p[j];
}
}
printf("%.7lf\n",pow(f[m],k));
}
return 0;
}
- 总结：
- 1.期望线性可加·
- 2.期望从后往前推。
- 3解决过程，找出各种情况乘上这种情况发生的概率，求和；
- 4.要初始化
临阵磨枪，不快也光！大家一起加油啊！！
