三角形最大路径和求解：C++代码故障排查请求

问题需求 #

• 给定数字三角形，找从顶部到底部的路径，使路径数字之和最大，规则如下：
  • 每步只能向下或向右下（对角线）移动
  • 三角形行数≤100
  • 数字为0-99的整数
• 示例：

  输入的三角形：
  7
  3 8
  8 1 0
  2 7 4 4
  4 5 2 6 5
  输出应为30（对应路径：7->3->8->7->5）

• 输入格式：先输入三角形高度（整数），再依次输入三角形的所有元素

代码问题分析 #

你的动态规划逻辑是正确的，但代码存在一个不符合C++标准的写法：int triangle[rows][rows];属于变长数组（VLA），而C++标准不允许用运行时变量作为数组的维度，这种写法会导致编译失败或者运行时出现未定义行为，这就是代码无法正常运行的核心原因。

修复后的代码 #

推荐使用C++的vector来存储三角形，它支持动态调整大小，且符合标准规范，同时保留原有的正确逻辑：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int rows;
    cin >> rows;
    // 创建二维vector，每行长度随行数递增
    vector<vector<int>> triangle(rows);
    for (int i = 0; i < rows; ++i) {
        triangle[i].resize(i + 1);
        for (int j = 0; j <= i; ++j) {
            cin >> triangle[i][j];
        }
    }
  
    // 从倒数第二层向上递推计算最大路径和
    for (int i = rows - 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] << endl;
    return 0;
}

补充说明 #

• vector会自动管理内存，不需要手动分配和释放，比动态数组更安全
• 使用std::max函数可以简化原有的if-else判断，让代码更简洁
• 原代码的动态规划思路没问题：从底部向上遍历，每个位置存储从该点到底部的最大路径和，最终顶部的数值就是全局最大路径和

内容的提问来源于stack exchange，提问作者ConTheNor