DP 一条龙
2025-01-11 20:30:57
发布于：北京
59阅读
0回复
0点赞
都是模板！！！
普通动规
小码王：初识动态规划
1.兔子数列
ACGO社区：兔子数列
这个太简单了
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,a[100];
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
a[1]=1;
a[2]=1;
for(int i=3;i<=n;i++){
a[i]=a[i-1]+a[i-2];
}
cout<<a[n];
return 0;
}
2.钞票问题
ACGO社区：钞票问题
思路（伪代码）
1、确定状态（用一维数组？二维数组？三维数组？能够确定唯一一个答案）
int dp[1000005];
//dp[i] 表示最少多少张钞票可以组成 i 元
2、推导状态转移方程
dp[i] = dp[i-1] + 1;
if(i >= 1)
dp[i] = min(dp[i],dp[i-1] + 1);
if(i >= 5)
dp[i] = min(dp[i],dp[i-5] + 1);
if(i >= 11)
dp[i] = min(dp[i],dp[i-11] + 1);
3、没的转移的要初始化
dp[0] = 0;
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
int c[3]={11,5,1};
int f[N],a[N];//f[i] 表示最少多少张钞票可以组成 i 元
int main(){
cin>>n;
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=1;i<=n;i++){
if(i>=5){
f[i]=min(f[i],f[i-5]+1);
}
if(i>=11){
f[i]=min(f[i],f[i-11]+1);
}
}
cout<<f[n];
return 0;
}
3.数字金字塔
ACGO社区：数字金字塔
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n;
int f[N][N],s[N][N],ans;//f[i][j] 表示从上往下走到（i，j）这个位置经过的最大数字和
//求 f[n][1 ~ n] 最大值
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>s[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
f[i][j]=max(f[i-1][j],f[i-1][j-1])+s[i][j];
}
}
for(int i=1;i<=n;i++){
ans=max(ans,f[n][i]);
}
cout<<ans;
return 0;
}
逆向DP（优化）
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n;
int f[N][N];//f[i][j] 表示从上往下走到（i，j）这个位置经过的最大数字和
//求 f[n][1 ~ n] 最大值
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>f[i][j];
}
}
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
f[i][j]+=max(f[i+1][j],f[i+1][j+1]);
}
}
cout<<f[1][1];
return 0;
}
4.不同的路径
ACGO社区：不同的路径
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int n,m;
long long f[N][N];
int main(){
cin>>m>>n;
f[1][1]=1;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(i==1&&j==1)continue;
f[i][j]+=f[i-1][j]+f[i][j-1];
}
}
cout<<f[m][n];
return 0;
}
注意这里要开long long 不然会爆
ACGO社区：传球游戏
#include<bits/stdc++.h>
using namespace std;
const int N=35;
int n,m;
int f[N][N];//f[i][j] 表示传了 j 次球最后在第 i 人手里的方案数
int main(){
cin>>n>>m;
f[1][0]=1;
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
if(i==1)f[i][j]+=f[n][j-1]+f[i+1][j-1];
else if(i==n)f[i][j]+=f[i-1][j-1]+f[1][j-1];
else f[i][j]+=f[i-1][j-1]+f[i+1][j-1];
}
}
cout<<f[1][m];
return 0;
}
线性动规（一维动规）
6.最长上升子序列
ACGO社区：最长上升子序列
二维代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int f[N][2],n,a[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
f[i][0]=max(f[i-1][0],f[i-1][1]);
//不在别的数后面
f[i][1]=1;
//不在别的数后面
for(int j=1;j<=i-1;j++){
if(a[j]<a[i])
f[i][1]=max(f[i][1],f[j][1]+1);
}
}
cout<<max(f[n][0],f[n][1]);
return 0;
}
优化一维版：
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int f[N],n,a[N],ma;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<=i-1;j++){
if(a[j]<a[i])
f[i]=max(f[i],f[j]+1);
}
ma=max(ma,f[i]);
}
cout<<ma;
return 0;
}
7.导弹拦截
ACGO社区：导弹拦截
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int f[N],n,a[N],ma;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<=i-1;j++){
if(a[j]>=a[i])
f[i]=max(f[i],f[j]+1);
}
ma=max(ma,f[i]);
}
cout<<ma;
return 0;
}
其实只用改一个符号
8.最长公共子序列
ACGO社区：最长公共子序列
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int f[N][N];
char a[N],b[N];
int main(){
cin>>(a+1);
cin>>(b+1);
int n=strlen(a+1);
int m=strlen(b+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i]!=b[j])
f[i][j]=max(f[i-1][j],f[i][j-1]);
else f[i][j]=f[i-1][j-1]+1;
}
}
cout<<f[n][m];
return 0;
}
9.编辑距离
ACGO社区：编辑距离
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int f[N][N];
char a[N],b[N];
int main(){
cin>>(a+1);
cin>>(b+1);
int n=strlen(a+1);
int m=strlen(b+1);
for(int i=1;i<=n;i++)f[i][0]=i;
for(int i=1;i<=m;i++)f[0][i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i]!=b[j])
f[i][j]=min({f[i-1][j],f[i-1][j-1],f[i][j-1]})+1;
else f[i][j]=f[i-1][j-1];
}
}
cout<<f[n][m];
return 0;
}
二维动规
10.房屋染色
ACGO社区：无
思路如下（伪代码）：
1、确定状态（用一维数组？二维数组？三维数组？能够确定唯一一个答案）
dp[i][j] 表示刷到第 i 个房子，第 i 个房子刷第 j 个颜色最小花费。
2、状态转移方程推导
（1）当前这个房子染红色
dp[i][1] = min(dp[i-1][2],dp[i-1][3]) + cost[i][1];
（2）当前这个房子染粉色
dp[i][2] = min(dp[i-1][1],dp[i-1][3]) + cost[i][2];
（1）当前这个房子染绿色
dp[i][3] = min(dp[i-1][1],dp[i-1][2]) + cost[i][3];
3、初始化(没有需要初始化的状态，或者dp[0][1] = dp[0][2] = dp[0][3] = 0)
4、答案为刷到第 n 个房子，第 n 个房子刷三种颜色最小花费值。
ans = min(dp[n][1],dp[n][2],dp[n][3]);
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,f[N][4],cost[N][4];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++){
cin>>cost[i][j];
}
}
for(int i=1;i<=n;i++){
//当前染红
f[i][1]=min(f[i-1][2],f[i-1][3])+cost[i][1];
//粉
f[i][2]=min(f[i-1][1],f[i-1][3])+cost[i][2];
//绿
f[i][3]=min(f[i-1][1],f[i-1][2])+cost[i][3];
}
cout<<min({f[n][1],f[n][3],f[n][2]});
return 0;
}
11.字符串种类
ACGO社区：无
思路如下（伪代码）：
1、确定状态（用一维数组？二维数组？三维数组？能够确定唯一一个答案）
dp[i] 表示前 i 个数字有多少种翻译方案。
2、状态转移方程推导
（1）第 i 个单独翻译。（没条件）
dp[i] = dp[i-1];
（2）第 i 个和 第 i-1 组合翻译。（s[i-1]*10 + s[i] < 26 && s[i] != 0）
dp[i] += dp[i-2];
3、初始化(dp[1] = 1,从第二项开始转移)
4、答案为dp[n]。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,f[N];
char a[N];
int main(){
cin>>(a+1);
n=strlen(a+1);
f[0]=1;
f[1]=1;
for(int i=2;i<=n;i++){
f[i]=f[i-1];
if((a[i-1]-'0')*10+a[i]-'0'<26&&a[i-1]!='0')
f[i]+=f[i-2];
}
cout<<f[n];
return 0;
}
12.挖地雷
ACGO社区：无
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n,mp[N][N],a[N],f[N],maxx;
//f[i] 表示走到第 i 个地窖获得的最多地雷数
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n-1;i++){
for(int j=i+1;j<=n;j++){
cin>>mp[i][j];
}
}
for(int i=1;i<=n;i++){
f[i]=a[i];
int ma=0;
for(int j=1;j<=i-1;j++){
if(mp[j][i]==1)
f[i]=max(f[i],f[j]+a[i]);
}
maxx=max(maxx,f[i]);
}
cout<<maxx;
return 0;
}
有帮助，赞一个