本文主要是介绍信息学奥赛一本通1258：【例9.2】数字金字塔，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1258：【例9.2】数字金字塔
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 44051 通过数: 26272
【题目描述】
观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。
在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。
【输入】
第一个行包含R(1≤R≤1000)，表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。
【输出】
单独的一行，包含那个可能得到的最大的和。
【输入样例】
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
【输出样例】
86
动态规划，我用的是从下往上推（逆推），也可以从上往下推（顺推）
逆推：
#include<bits/stdc++.h>
using namespace std;
int n,a[1001][1001];
int main()
{cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>a[i][j];}}for(int i=n-1;i>=1;i--){for(int j=1;j<=i;j++){a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]);}}
// cout<<"max="<<a[1][1];cout<<a[1][1];
}顺推：
#include<bits/stdc++.h>
using namespace std;
int n,a[1001][1001],cnt;
//int f[1001][1001];
int main()
{cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>a[i][j];a[i][j]=max(a[i-1][j],a[i-1][j-1])+a[i][j];cnt=max(cnt,a[i][j]);}}
// f[1][1]=a[1][1];
// 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])+a[i][j];
// cnt=max(cnt,f[i][j]);
// }
// }cout<<cnt;
}顺推也可以把注释的地方解开再把13和14行注释，我这样做可以节约一个1001*1001的int数组空间
这篇关于信息学奥赛一本通1258：【例9.2】数字金字塔的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
