class Solution {

public:

int min_val(vector<vector<int>>&triangle,int n,int index,vector<vector<int>>&dp){

if(n==0){

return triangle[n][0];

}

int maxi=1e9;

if(index<0 or index>=triangle[n].size()){

return 1e9;

}

if(dp[n][index]!=-1){

return dp[n][index];

}

return dp[n][index]=min(min_val(triangle,n-1,index,dp),min_val(triangle,n-1,index-1,dp))+triangle[n][index];

}

int minimumTotal(vector<vector<int>>& triangle) {

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

int min_sum=1e9;

for(int i=0;i<index;i++){

vector<vector<int>>dp(triangle.size(),vector<int>(index+1,-1));

min_sum=min(min_sum,min_val(triangle,triangle.size()-1,i,dp));

}

return min_sum;

}

};

top down dp

class Solution {

public:

int min_sum(vector<vector<int>>&triangle,int i,int j,vector<vector<int>>dp){

if(i==triangle.size()-1){

return triangle[i][j];

}

if(dp[i][j]!=-1){

return dp[i][j];

}

// explore direct and diagonal path

int d=triangle[i][j]+min_sum(triangle,i+1,j,dp);

int dg=triangle[i][j]+min_sum(triangle,i+1,j+1,dp);

return dp[i][j]=min(d,dg);

}

int minimumTotal(vector<vector<int>>& triangle) {

//vector<vector<int>>dp(triangle.size(),vector<int>(triangle.size(),-1));

int n=triangle.size();

int dp[n][n];

for(int i=0;i<n;i++){

dp[n-1][i]=triangle[n-1][i];

}

for(int i=n-2;i>=0;i--){

for(int j=i;j>=0;j--){

dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j];

}

}

return dp[0][0];

}

};