问题描述：给定一个由 n 行数字组成的数字三角形
试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

算法设计：对于给定的由 n 行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。

数据输入：文件 input.txt 提供输入数据。文件的第 1 行是数字三角形的行数 n(1 ≤ n ≤ 100)。
接下来的 n 行是数字三角形各行中的数字。所有数字在 0 ~ 99 之间。

结果输出：将计算结果输出到文件 output.txt。文件第 1 行中的数字是计算出的最大值。

#include <iostream>
using namespace std;

/*
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
巨tm经典数塔问题，dp[i][j]表示从第i行第j个数字到达最底层的所有路径能得到的最大和
*/
int n;//行数
int num[110][110];//存放数塔
int dp[110][110];

void init() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) { cin >> num[i][j];
        }
    }
}
void solve() {
    for(int i=1;i<=n;i++){ 
        dp[n][i]=num[n][i];//初始化,边界 
    } 
    for (int i = n-1; i>=1; i--) {
        for (int j = 1; j <= i; j++) {
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+num[i][j];//状态转移方程
        }
    }
    cout<<dp[1][1]<<endl;
}
int main() {
    init();
    solve();
    return 0;
}