/* Step-4 is to reduce the size of the cache.  What I do is use
   the last row of triangle as my cache.  That way, I don't have to
   set it! */

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle);
};

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