【LeetCode】Triangle

从三角形底部开始。到达每个元素的最小路径和为到上一层与它相邻两个元素最短路径和中较小者加上该元素的值。最后结果就是到第二层两个元素最短路径和中小者与第一行那个元素的和。

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