学步园

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

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

The minimum path sum from top to bottom is 11 (i.e.,
2 + 3 + 5 +
1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, wheren is the total number of rows in the triangle.

思路：

该结点能达到的最小值等于它的两个父结点能达到的最小值中较小的值加上本结点的值。

题解：

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        const int HEIGHT = triangle.size();
        vector<int> triangle_sum(HEIGHT);
        
        for(int i = 1; i <= HEIGHT; ++i)
        {
            for(int j = i - 1; j >= 0; --j)
            {
                int parent_value;
                
                if (j == 0 && i == 1)
                    parent_value = 0;
                else if (j == 0)
                    parent_value = triangle_sum[0];
                else if (j == i - 1)
                    parent_value = triangle_sum[j - 1];
                else
                    parent_value = min(triangle_sum[j - 1], triangle_sum[j]);
                
                triangle_sum[j] = triangle[i - 1][j] + parent_value;
            }
        }
        
        return *min_element(begin(triangle_sum), end(triangle_sum));
    }
};