题解 | 数字三角形

#include <bits/stdc++.h>
using namespace std;
//新手最易上手的方法
int main() {
    int n;
    cin >> n;
    vector<vector<int>>a(n + 1, vector<int>(n + 1, 0)), dp(n + 1, vector<int>(n + 1,
                     0));
    cin >> a[1][1];
    if (n == 1)cout << a[1][1];
    else {
        dp[1][1] = a[1][1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                cin >> a[i][j];
                if (j == 1 )dp[i][j] = dp[i - 1][j] + a[i][j];
                else if (j == i)dp[i][j] = dp[i - 1][j - 1] + a[i][j];
                else dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)ans = max(ans, dp[n][i]);
        cout << ans;
    }
}

//新手最易上手的方法