O(1)space solution using inspace traversal and using the array itself as dp storage


#1

Commenint Solution::minimumTotal(vector<vector > &A) {
int n=A.size();
for(int i=1;i<n;i++){
A[i][0]+=A[i-1][0];

   for(int j=1;j<A[i-1].size();j++){
       A[i][j]+=min(A[i-1][j-1],A[i-1][j]);
   }
   A[i][A[i].size()-1]+=A[i-1][A[i-1].size()-1];

}
int ans=A[n-1][0];
for(int i=1;i<A[n-1].size();i++){
ans=min(ans,A[n-1][i]);
}
return ans;
}t body goes here.