数字三角形(DP)

解题思路:

注意事项:

参考代码:

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

// 定义常量N，用于限制三角形的最大行数（此处设为30，可根据需求调整）
const int N = 30;

// 全局数组：
// a[i][j] 存储数字三角形第i行第j列的数值
// f[i][j] 存储从三角形顶部到第i行第j列的最大路径和
// 全局数组默认初始化为0，简化边界处理
int a[N][N], f[N][N];

int main (){
    int n;  // n表示三角形的行数
    cin >> n;  // 输入三角形的行数

    // 读入数字三角形的数据
    // 第i行有i个元素（j从1到i）
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= i; ++ j)
            cin >> a[i][j];

    // 初始化第一列的最大路径和
    // 每行第一列的元素只能从上方（上一行第一列）到达，因此路径和为上一行第一列的路径和加上当前元素值
    for(int i = 1; i <= n; ++ i)
        f[i][1] = f[i-1][1] + a[i][1];

    // 计算其余列（j ≥ 2）的最大路径和
    // 从第1行到第n行遍历，每行从第2列遍历到第i列（因第i行有i列）
    for(int i = 1; i <= n; ++ i)
        for(int j = 2; j <= i; ++ j){
            // 对于非第一列的元素，可从两个方向到达：
            // 1. 上方：上一行第j列（f[i-1][j]）
            // 2. 左上方：上一行第j-1列（f[i-1][j-1]）
            // 取两个方向的最大路径和，再加上当前元素值，即为当前位置的最大路径和
            f[i][j] = max(f[i-1][j], f[i-1][j-1]) + a[i][j];
        } 

    // 寻找最后一行的最大路径和（整个三角形的最大路径和一定在最后一行）
    int mx = 0;  // 存储最大值的变量
    for(int i = 1; i <= n; ++ i)
        mx = max(mx, f[n][i]);  // 比较最后一行所有元素的路径和

    cout << mx;  // 输出结果
    return 0;
}