**Description:**

https://leetcode.com/problems/triangle/#/description

**Algorithm:**

There are two ways:

Going from up to down or down to up.

There is no better ways. O(n^2) is the only choice.

**Code 1:**

`class Solution1 {`

public:

int minimumTotal(vector<vector<int>>& triangle) {

for (int i = triangle.size() - 2; i >= 0; i--)

{

for (int j = 0; j < i + 1; j++)

{

triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);

}

}

return triangle[0][0];

}

};

**Code 2:**

// go from up to down

`class Solution2 {`

public:

int minimumTotal(vector<vector<int>>& triangle) {

if (triangle.size() == 0) return 0;

if (triangle.size() == 1) return triangle[0][0];

int result = INT_MAX;

for (int i = 1; i < triangle.size(); i++)

{

triangle[i][0] += triangle[i - 1][0];

triangle[i][i] += triangle[i - 1][i - 1];

for (int j = 1; j < i; j++)

{

triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);

}

}

for (int j = 0; j < triangle.size();j++)

{

result = min(result, triangle[triangle.size() - 1][j]);

}

return result;

}

};

Timing & Space:

O(n^2) & O(1);