题解 | 数字三角形

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define quick ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int inf=0x3f3f3f3f,maxn=2e5+5,mod=998244353;
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
	return s*w;
}
void solve(){
    int n;n=read();
    vector<vector<int>>grid(n+1,vector<int>(n+1));
    vector<vector<int>>dp(n+1,vector<int>(n+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            grid[i][j]=read();
            if(i==n){
                dp[i][j]=grid[i][j];
            }
        }
    }
    //dp[i][j]=max(dp[i][j]+dp[i-1][j-1],dp[i][j]+dp[i-1][j])
    for(int i=n-1;i>0;i--){
        for(int j=1;j<=i;j++){
            dp[i][j]=max(dp[i+1][j+1],dp[i+1][j]);
            dp[i][j]+=grid[i][j];
        }
    }
    cout<<dp[1][1]<<endl;
}
signed main(){
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}