题解 | 数字三角形

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;cin>>n;
    vector<vector<int>> nums(n+1,vector<int>(n+1)); 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>nums[i][j];
        }
    }

    vector<vector<int>> dp(n+1,vector<int>(n+1)); 
    dp[1][1] = nums[1][1];

    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(j==1) dp[i][j] = dp[i-1][j] + nums[i][j];
            else if(i == j) dp[i][j] = dp[i-1][j-1] + nums[i][j];
            else dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + nums[i][j];
        }
    }
    
    cout<<*max_element(dp[n].begin(),dp[n].end());

}
// 64 位输出请用 printf("%lld")