dp基础
2024-12-05 20:30:42
发布于：广东
6阅读
0回复
0点赞
1.斐波那契数列
#include<bits/stdc++.h>
using namespace std;
//创建数组描述序列各个阶段的状态 状态最优时是固定的
long long dp[110] ;
int n;
//dp 1.创建数组-描述各个阶段的状态2.寻找状态转移方程
int main(){
cin>>n;
dp[1]=dp[2]=1;
for(int i=3;i<=n;i++)dp[i]=dp[i-1]+dp[i-2];
cout<<dp[n]<<endl;
return 0;
}
2.找钱
#include<bits/stdc++.h>
using namespace std;
int dp[2000001],n;//dp[i]:i元钱需要的最少张数
int main(){
cin>>n;
dp[1]=1;
dp[0]=0;
//i=2开始确定各个阶段的状态
for(int i=2;i<=n;i++){
if(i<5)dp[i]=dp[i-1]+1;
else if(i<11)dp[i]=min(dp[i-1],dp[i-5])+1;
else dp[i]=min( min(dp[i-1],dp[i-5]) ,dp[i-11])+1;
}
printf("%d",dp[n]);//dp【n】 ：给客户找n元钱需要的最少张数
return 0;
}
3.数字三角形
#include<bits/stdc++.h>
using namespace std;
int dp[1001][1001],sq[1001][1001];
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>sq[i][j];
}
}
/*dp[1][1]=sq[1][1];
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
if(j==1)dp[i][j]=dp[i-1][j]+sq[i][j];
else dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+sq[i][j];
}
}
int ans=-0x7f7f7f;
for(int i=1;i<=n;i++)ans=max(ans,dp[n][i]);
printf("%d",ans);*/
for(int i=n;i>=1;i--){
for(int j=1;j<=i;j++){
dp[i][j]+=max(dp[i+1][j],dp[i+1],[j+1]);
}
}
cout<<dp[1][1];
return 0;
}
4.区间子序列最大值
#include<bits/stdc++.h>
using namespace std;
int dp[110],a[110],n,ans=-0x7f7f7f;//dp[i]右端为i的连续非空子序列 最大值
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=i;i<=n;i++){
dp[i]=max(dp[i]-1+a[i],a[i]);//状态转移方程
ans=max(ans,dp[i]);
}
printf("%d",ans);
return 0;
}
这里空空如也
有帮助，赞一个