题解
每个格子只能从他上面的格子
和斜上方的格子
两个格子推导而来
f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
const int N=510;
int f[N][N],a[N][N],n;
void init(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int main(void){
init();
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
memset(f,-0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=max(f[i-1][j]+a[i][j],f[i-1][j-1]+a[i][j]);
}
}
int res=-0x3f3f3f3f;
for(int i=1;i<=n;i++){
res=max(res,f[n][i]);
}
cout<<res;
}