From Acwing
第一行包含整数n,表示数字三角形的层数。
接下来n行,每行包含若干整数,其中第 i 行表示数字三角形第 i 层包含的整数。
输出一个整数,表示最大的路径数字和。
1≤n≤500,
?10000≤三角形中的整数≤10000
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
30
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510;
int n,w[N][N],f[N][N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>w[i][j];
}
}
for(int i=1;i<=n;i++) f[n][i]=w[n][i];
for(int i=n-1;i;i--){
for(int j=1;j<=i;j++){
f[i][j]=max(f[i+1][j],f[i+1][j+1])+w[i][j];
}
}
cout << f[1][1] << endl;
return 0;
}
原文:https://www.cnblogs.com/chickenleg/p/14269739.html