Top down approach with linear time and constant extra space


#1

Please inform if the solution is wrong.

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

}


#2

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.