Memoization approach


#1

int find(vector<vector > &A,int cur,int r,int l,vector<vector > &vec){
if(l>r)return 0;
if(vec[l][cur]!=-1)return vec[l][cur];
vec[l][cur]= A[l][cur] + min(find(A,cur,r,l+1,vec),find(A,cur+1,r,l+1,vec));
return vec[l][cur];
}

int Solution::minimumTotal(vector<vector > &A) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
vector<vector > vec( A.size() , vector (A.size(), -1));
return find(A,0,A.size()-1,0,vec);

}