题解 | 数字三角形

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    vector<vector<int>>dp(n+1,vector<int>(n+1,0));
    vector<vector<int>>a(n+1,vector<int>(n+1,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    int ans=-100000;
    dp[1][1]=a[1][1];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(j==i)dp[i][j]=dp[i-1][j-1]+a[i][j];
            else if(j==1)dp[i][j]=dp[i-1][j]+a[i][j];
            else dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
            if(i==n)ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans;
    return 0;
}

新手练题，听说写题解可以锻炼自己的能力所以尝试一下，也是给我浅薄的理解。依旧先分析一下雷霆题目，一个点可以向左下或向右下走，找一条路让和最大，从贪心的角度，就是每次都走最大的,状态转移方程，三角形涉及图形，故而可以用二维数组存储,判断范围，最右侧的点只能从左上角转移,同理最右侧的点只能是他的头上和他的右侧。做三个单独的条件判断，得解；

tip:可以选择设一个变量来维护最大值，但记得只能在最后一行这样做，因为三角形的数不恒正，中途会加了负数变小，与最后的最大值产生出入。