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