class Solution {
public:
    int helperFunction(vector<vector<int>> & triangle, vector<vector<int>> & dp, int pos, int row){
        if(row == triangle.size()) return 0;
        if(dp[row][pos] > 0) return dp[row][pos] + triangle[row][pos];
        
        dp[row][pos] =  min(helperFunction(triangle, dp, pos, row + 1), helperFunction(triangle, dp,  pos + 1, row + 1));
        
        return dp[row][pos] + triangle[row][pos];
    }
    
    int minimumTotal(vector<vector<int>>& triangle) {
        
        if(triangle.size() == 0) return 0;
        vector<vector<int>> dp;
        for(int i = 0; i < triangle.size(); i++){
            dp.push_back(vector<int>(triangle[i].size(), 0));
        }
        int ans =  helperFunction(triangle, dp, 0, 0);
        return ans;
        
    }
};