一、问题描述 给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的节点上。 二、​​C++​​解决方案（带注释）

#include <vector>
#include <algorithm>
using namespACe std;

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        // 从倒数第二层开始向上递推
        for (int i = n - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                // 当前节点的最小路径和 = 当前值 + 下一层相邻两个节点的较小值
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
            }
        }
        return triangle[0][0]; // 返回顶点的最小路径和
    }
};

三、​​算法​​解析

1. ​动态规划​思想：采用自底向上的方法，避免重复计算
2. ​时间复杂度​：O(n²)，其中n是三角形的行数
3. 空间复杂度：O(1)，直接在原数组上修改

四、​​优化​​思路

1. 可以使用一维数组进一步优化空间复杂度
2. ​​边界条件处理​​：当三角形为空时直接返回0

转自：力扣120题终极攻略：动态规划解三角形最小路径和（C++实现）