# My C++ solution, O(n) space, accepted for 8ms

• ``````class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
int m=triangle.size();
vector<int> res;
res.push_back(triangle[0][0]);

for(int i=1;i<m;i++){
vector<int> temp(i+1);
temp[0]=res[0]+triangle[i][0];
temp[i]=res[i-1]+triangle[i][i];

for(int j=1;j<i;j++)
temp[j]=res[j-1]>res[j]?(res[j]+triangle[i][j]):(res[j-1]+triangle[i][j]);

res=temp;
}

int min=res[0];
for(int j=1;j<m;j++){
if(res[j]<min)
min=res[j];
}
return min;
}
};
``````

I use O(n) space instead of O(1) space, because I don't think modifying the original data "triangle" is always a good choice.

• But actually `res` and `temp` both uses O(N) space right?

• I modify your code and remove the `temp` to use less space.

``````class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
int m=triangle.size();
vector<int> res(m,0);
res[0]=triangle[0][0];

for(int i=1;i<m;i++){
res[i]=res[i-1]+triangle[i][i];
for(int j=i-1;j>0;j--)
res[j]=res[j-1]>res[j]?(res[j]+triangle[i][j]):(res[j-1]+triangle[i][j]);

res[0]=res[0]+triangle[i][0];
}

int min=res[0];
for(int j=1;j<m;j++){
if(res[j]<min)
min=res[j];
}
return min;
}
};``````

• I am lazy. in place solution (sometimes it's not good for destroying the original input)

``````int minimumTotal(vector<vector<int> > &triangle) {
if (triangle.empty()) return 0;
for (int i = triangle.size() - 2; i >=0; --i) {
for (int j = 0; j < triangle[i].size(); ++j) {
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
}
}
return triangle[0][0];
}
``````

OK, now it's the O(n) space solution, just add one line of code

``````int minimumTotal(vector<vector<int> > &triangle) {
if (triangle.empty()) return 0;
vector<int> v(triangle.back());
for (int i = triangle.size() - 2; i >=0; --i) {
for (int j = 0; j < triangle[i].size(); ++j) {
v[j] = min(v[j], v[j+1]) + triangle[i][j];
}
}
return v[0];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.