题目描述
数字三角形
想法
寻找当前行的最优解
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=500,INF=0x3f3f3f3f;
int a[N][N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=0;j<=i+1;j++){
a[i][j]=-INF;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
for(int i=1;i<n;i++){
for(int j=1;j<=i+1;j++){
//cout<<a[i+1][j]<<" + "<<max(a[i][j-1],a[i][j])<<" ";
a[i+1][j]+=max(a[i][j-1],a[i][j]);
}
//cout<<endl;
}
int res = 0;
for(int i=1;i<=n;i++){
res = max(res,a[n][i]);
}
cout<<res<<endl;
}