120 Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is
11(i.e.,2+3+5+1= 11).Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
Complexity: O(n) time, O(2sqrt(n)) space. Given N elements in the triangle matrix, I add 0s to both ends of matrix).
The Idea: Build an accumulation matrix (dynamic programming) that follows the rule of what is considered to be an adjacent element. To make things easier for ourselves, we add
INT_MAX to both ends of our triangle matrix (refine_triangle_matrix). Keep in mind that this doubles the time complexity of our code, but we do this as a hack in order to avoid having to define separate subroutines for the edges of the triangle. Instead, we define a single subroutine that iterates through this new matrix. The minimum sum then follows to be minimum element in the bottom row.This would be the accumulation matrix for the example above.
0: 2147483647 2 2147483647
1: 2147483647 5 6 2147483647
2: 2147483647 11 10 13 2147483647
3: 2147483647 15 11 18 16 2147483647
Related algorithms: Seam Carving (computer vision)
void refine_triangle_matrix(vector<vector<int>> &triangle)
{
if (triangle.empty()) return;
const size_t col_size = triangle.size();
const size_t row_size = triangle.at(0).size();
// inserting int max since we are minimizing the
// entire thing (hence these additions get ignored)
for (int i = 0; i < col_size; i++) {
triangle.at(i).push_back(INT_MAX);
auto it = triangle.at(i).begin();
triangle.at(i).insert(it, INT_MAX);
}
}
int minimumTotal(vector<vector<int>>& triangle)
{
if (triangle.empty()) return 0;
refine_triangle_matrix(triangle);
const size_t col_size = triangle.size();
for (int i = 1; i < col_size; i++) {
for (int j = 1; j < triangle.at(i).size() - 1; j++) {
int top_left = triangle[i - 1][j - 1];
int top_right = triangle[i - 1][j];
triangle[i][j] += min(top_left, top_right);
}
}
//print2d(triangle); pause();
return *min_element(triangle.at(col_size - 1).begin() + 1, triangle.at(col_size - 1).end() - 1);
}
// testing
int main()
{
vector<vector<int>> tri =
{
{ 2 },
{ 3,4 },
{ 6,5,7 },
{ 4,1,8,3 }
};
cout << minimumTotal(tri) << endl;
}
Last modified 4yr ago