P1216 数字三角形（洛谷刷题记）

题目

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

        7 3   8 8   1   0 2   7   4   4 
4   5   2   6   5 

范围

1 <= n <= 1000，所有输入数在区间 [0,100] 内

分析

对于每个数来说，它只能来自于它的左上角那个数以及正上方那个数，故只需要将这二者取 max 即可，最后再将计算所得的最后一行所有结果取 max 即可。

代码

#include<bits/stdc++.h>
using namespace std;const int N = 1010;
int n;
int a[N][N] = {0};
int f[N][N] = {0};int main()
{cin >> n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin >> a[i][j];f[i][j] = a[i][j];f[i][j] = a[i][j] + max(f[i-1][j],f[i-1][j-1]);}}int res=0;for(int i=1;i<=n;i++)res = max(res,f[n][i]);cout << res << endl;return 0;
}

原题链接 洛谷 P1216 数字三角形