题解 | 数字三角形

#include <algorithm>
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
int main() {
    int a;
    cin>>a;
    vector<vector<int>>s(a+1,vector<int>(a+1,0));
    for(int i=1;i<=a;i++){
        for(int j=1;j<=i;j++){
            cin>>s[i][j];
        }
    }
    vector<vector<long long>>dp(a+1,vector<long long>(a+1,0));
    dp[1][1]=s[1][1];
    for(int i=2;i<=a;i++){
        for(int j=1;j<=i;j++){
            if(j==1)dp[i][j]=dp[i-1][j]+s[i][j];
            else if(j==i)dp[i][j]=dp[i-1][j-1]+s[i][j];
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+s[i][j];
        }
    }
    long long zuida=dp[a][1];
    for(int i=2;i<=a;i++){
        zuida=max(zuida,dp[a][i]);
    }
    cout<<zuida<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")