/* Now I add a cache. No other comments needed*/

class Solution {
public:
    vector <vector <int> > *t;
    int minimumTotal(vector<vector<int>>& triangle);
    int dp(int row, int col);
    vector <vector <int> > cache;
};

int Solution::minimumTotal(vector<vector<int>>& triangle)
{
    size_t i;
    
    cache.resize(triangle.size());
    for (i = 0; i < cache.size(); i++) cache[i].resize(i+1, 2000*10000);
    t = &triangle;
    return dp(0, 0);
}

int Solution::dp(int row, int col)
{
    int z, o;
    
    if (row == t->size()-1) return (*t)[row][col];
    if (cache[row][col] != 2000*10000) return cache[row][col];
    z = dp(row+1, col);
    o = dp(row+1, col+1);
    cache[row][col] = (*t)[row][col] + ((z < o) ? z : o);
    return cache[row][col];
}