# 5 lines c++, short and sweet

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

• Very smart solution, though the parameter triangle modified is a side effect. Anyway, quite smart one! Here is my direct solution using O(n) space.

``````class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle)
{
int rowSize = triangle.size();
if(!rowSize) return 0;
int cur[rowSize]{0}, pre[rowSize]{0};
pre[0] = triangle[0][0];
for(int r = 1; r < rowSize; ++r)
{
for(int c = 0; c < triangle[r].size(); ++c)
{
if(c == 0) cur[0] = pre[0]+triangle[r][0];
else if(c == triangle[r].size()-1) cur[c] = pre[c-1]+triangle[r][c];
else cur[c] = min(pre[c], pre[c-1])+triangle[r][c];
}
memcpy(pre, cur, sizeof(int)*rowSize);
}
int minSum = INT_MAX;
for(int i = 0; i < rowSize; ++i) minSum = min(minSum, pre[i]);
return minSum;
}
};``````

• @Yuanhui Why does this solution not work for top-bottom approach ?

• @sujiths52 If you go from top to bottom, you have to check the minimum in the last row in the end. But I think it works.

• ``````class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
for(int i = 1; i < triangle.size(); i++)
for(int j = 0; j <= i; j++)
if (j == 0) triangle[i][0] += triangle[i-1][0];
else if (j == i) triangle[i][j] += triangle[i-1][j-1];
else triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]);
int mini = INT_MAX;
for (int i = 0; i < triangle.size(); i++) {
mini = min(mini, triangle[triangle.size()-1][i]);
}
return mini;
}
};
``````

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