class Solution {

public:

```
int minimumTotal(vector<vector<int>>& triangle) {
if(triangle.empty()){
return 0;
}
int size = triangle.size();
vector<int> sum(triangle[size-1]); // O(n) extra space
for(int i = size-2; i > -1; i--){ // sum from bottom to top
for(int j = 0; j < size; j++){
sum[j] = min(sum[j], sum[j+1]) + triangle[i][j];
}
}
return sum[0];
}
```

};