目录

题目描述：

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

示例：

给定三角形：

[     [2],    [3,4],   [6,5,7],  [4,1,8,3]]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

• 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

---

解法：

class Solution {public:    int minimumTotal(vector
    
     
      >& triangle) {        int n = triangle.size();        if(n == 0){            return 0;        }else{            vector
      
        res(n+2, INT_MAX);            res[1] = triangle[0][0];            for(int i = 1; i < n; i++){                for(int j = i; j >= 0; j--){                    res[j+1] = min(res[j], res[j+1]) + triangle[i][j];                }            }                        int min_val = INT_MAX;            for(int val : res){                min_val = min(val, min_val);            }            return min_val;        }    }};