class Solution {
      
public:
    int dp[201][201];
    Solution(){
    memset(dp,INT_MAX,sizeof(dp));}
    int func(vector<vector<int>>& triangle,int n,int i,int j){
        if(i>=n){
            return 0;
        }
       // else if(i==(n-1)){
        //    return dp[i][j]=triangle[i][j];
        //}
        if(dp[i][j]!=INT_MAX){
            return dp[i][j];
        }
            return dp[i][j]=triangle[i][j]+min(func(triangle,n,i+1,j),func(triangle,n,i+1,j+1));
    }
    int minimumTotal(vector<vector<int>>& triangle) {
        int n=triangle.size();
       //  for(int i=0;i<200;i++)
        //{
          //  for(int j=0;j<200;j++)
           // {
             //   dp[i][j]=INT_MAX;
            //}
        //}   
        int ans=func(triangle,n,0,0);
        return ans;
    }
};