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, where n is the total number of rows in the triangle.Triangle

code

class Solution
{
public:
    int minimumTotal(vector<vector<int>>& triangle)
    {
        if(triangle.empty()||triangle.at(0).empty())
            return -1;

        for(int i=1;i<triangle.size();++i)
        {
            for(int j=0;j<triangle.at(i).size();++j)
            {
                if(j==0)
                    triangle.at(i).at(j)+=triangle.at(i-1).at(j);
                else if(j==triangle.at(i).size()-1)
                    triangle.at(i).at(j)+=triangle.at(i-1).at(j-1);
                else
                    triangle.at(i).at(j)+=min(triangle.at(i-1).at(j),triangle.at(i-1).at(j-1));
            }
        }
        return *min_element(triangle.at(triangle.size()-1).begin(),triangle.at(triangle.size()-1).end());
    }
};