网站子站建设自查报告,企业微信app下载安装官网电脑版,北京优化核酸检测,网络营销师是什么题目网址 1258#xff1a;【例9.2】数字金字塔 首先解这道题我们第一眼想到是不是暴力#xff0c;但是暴力的话是O(n!)的时间复杂度#xff0c;很明显#xff0c;会超时。那怎么办呢#xff1f;不如我们把他分成若干子问题把#xff0c;就像分治那样。 首先我们想得到答案…题目网址 1258【例9.2】数字金字塔 首先解这道题我们第一眼想到是不是暴力但是暴力的话是O(n!)的时间复杂度很明显会超时。那怎么办呢不如我们把他分成若干子问题把就像分治那样。 首先我们想得到答案必须经过最后一层的筛选最后一层的每个数都是加上自己再加上上一层达到的最大值的所以对于最后一层的每一个点向上推到达上一层后上一层的每个数也都是加上自己后再加上一层过来的最大值过来的……最后推到最顶层这时我们就能根据规律再反推得到答案。而这种思路就是动态规划–递推
那么很明显了根据上一段的规律我们能写出代码 初始化
int n;
int a[1050][1050];
int dp[1050][1050];
......
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cinn;
for(int i1;in;i){for(int j1;ji;j){cina[i][j];}
}重点 dp
for(int i1;in;i){for(int j1;ji;j){dp[i][j]max(dp[i-1][j],dp[i-1][j-1]); //dp[i][j]是由本身的数过来的数中最大的数dp[i][j]a[i][j];}
}
int mx0;
for(int i1;in;i){ //得出最大值mxmax(mx,dp[n][i]);
}最后放下总代码
#include bits/stdc.h
using namespace std;
int n;
int a[1050][1050];
int dp[1050][1050];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cinn;
for(int i1;in;i){for(int j1;ji;j){cina[i][j];}
}
for(int i1;in;i){for(int j1;ji;j){dp[i][j]max(dp[i-1][j],dp[i-1][j-1]);dp[i][j]a[i][j];}
}
int mx0;
for(int i1;in;i){mxmax(mx,dp[n][i]);
}
coutmx;return 0;
}最后大家如果不了解dp可以点这里 dp动态规划的基本
