欧拉三角形最大路径和问题：如何定位求和路径元素

欧拉三角形问题要求找出从首元素到末行任意元素的最大路径和。输入示例：5（行数），后续三角形元素为：7；3 8；8 1 0；2 7 4 4；4 5 2 6 5。输出示例：30 7 3 8 7 5。

我已经能计算出最大和（如30），但无法正确找出所有参与求和的元素，相关C++代码片段如下：

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int m;
    cin >> m;
    int tri[m][m];
    for(int i=0; i < m; ...

别担心，这问题太常见了——你现在的代码应该只实现了动态规划求最大和的逻辑，但没记录每一步的选择方向，自然没法回溯出具体路径。我来给你调整下代码，补上路径追踪的功能：

解决思路 #

1. 新增路径标记数组：创建一个和三角形同尺寸的path数组，用来记录每个位置的最大路径是从下方哪个位置来的（比如用0表示正下方，1表示右下方）。
2. 动态规划+路径记录：从倒数第二行向上遍历，计算每个位置的最大和时，同步记录选择的方向。
3. 回溯路径：从三角形顶部开始，根据path数组的标记一步步往下走，收集所有路径元素。

修改后的完整代码 #

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int m;
    cin >> m;
    // 用vector替代变长数组，避免部分编译器兼容性问题
    vector<vector<int>> tri(m, vector<int>(m, 0));
    vector<vector<int>> path(m, vector<int>(m, 0)); // 0选正下方，1选右下方

    // 输入三角形元素
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j <= i; ++j) {
            cin >> tri[i][j];
        }
    }

    // 从倒数第二行向上计算最大和，同时记录路径选择
    for (int i = m - 2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            if (tri[i+1][j] > tri[i+1][j+1]) {
                tri[i][j] += tri[i+1][j];
                path[i][j] = 0;
            } else {
                tri[i][j] += tri[i+1][j+1];
                path[i][j] = 1;
            }
        }
    }

    // 回溯收集原始路径元素
    vector<int> result_path;
    int current_j = 0;
    // 先加入顶部原始元素（动态规划后tri[0][0]是总和，减去下一层的累计和得到原始值）
    result_path.push_back(tri[0][0] - tri[1][current_j + path[0][current_j]]);
    for (int i = 0; i < m - 1; ++i) {
        current_j += path[i][current_j];
        // 还原当前层原始元素：如果不是最后一行，就减去下一层的累计和
        int original_val = (i+2 < m) ? tri[i+1][current_j] - tri[i+2][current_j + path[i+1][current_j]] : tri[i+1][current_j];
        result_path.push_back(original_val);
    }

    // 输出结果：最大和 + 路径元素
    cout << tri[0][0] << " ";
    for (int num : result_path) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

代码说明 #

• 用vector替代了C++中兼容性较差的变长数组int tri[m][m]，适配更多编译器。
• 因为动态规划过程中tri数组被修改成了累计和，所以回溯时需要通过减去下一层的累计和来还原原始元素值。
• 输入示例数据后，会输出30 7 3 8 7 5，完全符合题目要求。

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