/* Step 3 -- remove the recursion by setting the cache from high
   rows down to 0, then returning the answer for 0,0. */

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

int Solution::minimumTotal(vector<vector<int>>& triangle)
{
  int i, j;
  int z, o, answer;
  
  cache.resize(triangle.size());

  /* Set up the last row of the cache from the last row of triangle. */

  i = (int) cache.size()-1;
  cache[i] = triangle[i];

  /* Now repeat your previous calculation, getting answers from the cache. */

  for (i--; i >= 0; i--) {
    for (j = 0; j <= i; j++) {
      z = cache[i+1][j];
      o = cache[i+1][j+1];
      answer = triangle[i][j] + ((z < o) ? z : o);
      cache[i].push_back(answer);
    }
  }
  return cache[0][0];
}