数字金字塔，记忆化dfs，点进来吧万一就看懂了呢

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 全局变量声明
int r, sss; // r表示三角形的行数，sss用于存储最终结果
int s[1100][1100]; // 存储输入的三角形数据
int z[1100][1100]={0}; // 存储动态规划中间结果
int dfs(int x, int y){
    // 如果z[x][y]已经计算过，直接返回其值
    if(z[x][y] != 0){
        return z[x][y];
    }
    // 如果到达最后一行，直接将当前值赋给z[x][y]
    if(x == r){
        z[x][y] = s[x][y];
    }
    else{
        // 递归计算下一行两个可能位置的最大值，并加上当前值赋给z[x][y]
        z[x][y] = s[x][y] + max(dfs(x+1, y), dfs(x+1, y+1));
    }
    return z[x][y]; // 返回计算结果
}
int main(){
    cin >> r; // 读取三角形的行数
    // 读取三角形的数据
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= i; j++){
            cin >> s[i][j];
        }
    }
    sss = dfs(1, 1); // 调用dfs函数计算最大路径和
    cout << sss << endl; // 输出结果
    return 0;
}