#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; // 三角形的行数
    cin >> n;
    
    // 创建二维数组存储三角形数字
    int triangle[n][n];
    
    // 输入三角形数据
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            cin >> triangle[i][j];
        }
    }
    
    /* 从底部向上计算最大路径和
       思路：每个位置的最大和等于它本身加上
       下方左右两个位置中较大的那个值 */
    for(int i = n-2; i >= 0; i--) {
        for(int j = 0; j <= i; j++) {
            // 选择下方左右中较大的值加到当前位置
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]);
        }
    }
    
    // 顶部存储的就是最大路径和
    cout << triangle[0][0];
    
    return 0;
}

逆向思维+贪心+递推思想 要求从最高点到底部任意处的最大路径。但是在解决问题时，应当逆向思维， 从最底层开始推导，如图所示。设有一个结构和三角形a完全相同的三角形b，用于描述第5排（最后一排）到底部的最大路径。由于第5排到底部只需要经过第5排，所以，各个位置到底部的最大路径就是元素内部的数字。