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.

int minimumTotal(vector<vector<int>>& triangle) { // time: O(n^2); space: O(n^2)
    int n = triangle.size();
    vector<vector<int> > sum(n, vector<int>(n, 0));
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i; j >= 0; --j) {
            sum[i][j] = (i == n - 1 ? 0 : min(sum[i + 1][j], sum[i + 1][j + 1])) + triangle[i][j];
            // cout << "i: " << i << ", j: " << j << ", sum[i][i]: " << sum[i][j] << endl;
        }
    }
    return sum.front().front();
}

// Space optimized dynamic programming
int minimumTotal(vector<vector<int>>& triangle) { // time: O(n^2); space: O(n)
    int n = triangle.size();
    vector<int> sum(n, 0);
    for (int i = n - 1; i >= 0; --i) {
        int bottomRight = i == n - 1 ? 0 : sum[i + 1];
        for (int j = i; j >= 0; --j) {
            int bottom = sum[j];
            sum[j] = min(sum[j], bottomRight) + triangle[i][j];
            bottomRight = bottom;
        }
    }
    return sum.front();
}