# 120. Triangle

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);