// Author : Murat Gevrekci
// Date : 20160915
/**********************************************************************************
 This problem can be used without any extra space !
 First observation is that a pyramid can be visualized aligned to left without loss of information
 [a],
 [b,c],
 [d,e,f],
 Second observation is that result can be propagated from bottom of the pyramid to the top layer.
 Number of elements to operate narrows down by one at each layer. At each element we decide to select which element from the bottom layer.
 Bottom layer is not processed but used as the initial elements.

[a], [a], [a+min(b+min(d,e),c+min(e+f)) ]

[b,c], > [b+min(d,e), c+min(e+f) ], > [b+min(d,e), c+min(e+f) ],

[d,e,f], [d, e , f ], [d, e, f],
 result is > "a+min(b+min(d,e),c+min(e+f))"
**********************************************************************************/
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int height = triangle.size();
//Return the top of the pyramid if tree is single layer
if (height==1)
{
return triangle[0][0];
}
//Propagate the sum from bottom to to top, result will be stored at the top of the pyramid
for(int heightIndex=height2;heightIndex>=0;heightIndex)
{
int length = triangle[heightIndex].size();
//Decide to pick which element for the elements in between
for(int Index=0;Index<length;Index++)
{
triangle[heightIndex][Index] += min(triangle[heightIndex+1][Index],triangle[heightIndex+1][Index+1]);
}
}
return triangle[0][0]; // return the top of the pyramid
}
};