O(n) space and O(n^2) time solution in C++


#1

int Solution::minimumTotal(vector<vector > &A) {
int n=A.size();
int dp[n];
for(int i=0;i<n;i++){
dp[i]=A[n-1][i];
}
for(int i=n-2;i>=0;i–){
for(int j=0;j<n;j++){
dp[j]=A[i][j]+min(dp[j],dp[j+1]);
}
}
return dp[0];
}