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 is11(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;
}