假期的周末晚上，刷起来leetcode，2021年第一题，动态规划，走你。

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

这里空间复杂度O(n)，最后一行作为mini的初始值，然后每次根据下一行更新mini，更新到第一行后mini[0]保存的即是最小值。
运行结果:

Runtime: 8 ms, faster than 88.88% of C++ online submissions for Triangle.
Memory Usage: 8.9 MB, less than 39.91% of C++ online submissions for Triangle.