Top down approach with linear time and constant extra space


Please inform if the solution is wrong.

int Solution::minimumTotal(vector<vector<int> > &A) { 
for(int i=1;i<A.size();i++){
    for(int j=1;j<A[i].size()-1;j++){
        A[i][j]+= min(A[i-1][j],A[i-1][j-1]);
return *min_element(A[A.size()-1].begin(),A[A.size()-1].end());



Code is OK. But you are wrong when you say this is linear time. Input size is the number of rows and any-possible code has to run n-choose-2 times at-least.