# 12ms c++ solution with O(n) additional space

• ``````class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();

if (n <= 0) return 0;

vector<int> d(triangle[n-1].size(), INT_MAX);       // caculate current level score
vector<int> temp(triangle[n-1].size(), INT_MAX);    //backup up level score
d[0] = triangle[0][0];
temp = d;
for (int i = 1; i < n; i++) {
for (int j = 0; j < triangle[i].size(); j++) {
if (j == 0) {   // left corner
d[j] = temp[j] + triangle[i][j];
} else if (j == triangle[i].size() - 1) {   // right corner
d[j] = temp[j-1] + triangle[i][j];
} else {
d[j] = min(temp[j-1], temp[j]) + triangle[i][j];
}
}
temp = d;
}

// get the minimal score
int min_val = INT_MAX;
for (int i = 0; i < d.size(); i++){
if (d[i] < min_val)
min_val = d[i];
}

return min_val;
}
};``````

• A simpler one:

``````class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if(triangle.size() == 0) return 0;

vector<int> v1 = triangle[triangle.size()-1];

for (int row = triangle.size()-2; row >=0; row--) {
vector<int> v2 = v1;
for(int k = 0; k < triangle[row].size(); k++) {
v2[k] = triangle[row][k] + min(v1[k], v1[k+1]);
}
v1.swap(v2);
}
return v1[0];
}
};``````

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