[LeetCode] Triangle

Problem Statement (link):

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.

Analysis:
This problem is similar to find-shortest-path problem, it's obvious a DP.

I tried DFS first - as in Sol 1, using an int to store the smallest sum we got so far, even though it uses O(1) space, it has O(n^2) time complexity and overlapped sub-problems.

I turned to DP. It is obvious we can use a 2-D dp matrix to record all the smallest sum up to some number, where dp[i][j] record the smallest sum to j-th entry of i-th vector in triangle. However, the problem asks for O(n) space complexity.

Think about bottom-up approach instead. We use a length-n dp vector to record the smallest sum up to some number as well, where n is length of triangle. But this time, we update/re-use the dp vector iteratively as we scan through the triangle toward the pinnacle. Thus, for triangle[i], we only need the first [0 : i] of the vector.

How about the transition function? Well, except for the bottom row, where dp[i] equals each entry of the vector, we compute the new dp[i] by adding the number itself to the smallest value of its adjacent two number in the row below. We repeat this process until we reach the pinnacle. See Sol 2 for code.

Code:
Sol 1 - DFS (TLE)

int minimumTotal(vector<vector<int> > &triangle) {
    if (triangle.empty()) return 0;
    int n=triangle.size();
    //vector<int> minVec(n,INT_MAX);
    int m=INT_MAX;
    recur(triangle, m, 0, 0, 0);
    return m;
}
// i-row num; j-index in each vector
void recur(vector<vector<int>>& triangle, int& m, int val, int i, int j) {
    if (i==triangle.size()) {
        m=min(m,val);
        return;
    }
    recur(triangle, m, triangle[i][j]+val, i+1, j);
    recur(triangle, m, triangle[i][j]+val, i+1, j+1);
}

Sol 2 - DP

class Solution {
public:
    // try 2 - DP
    int minimumTotal(vector<vector<int> >&triangle) {
        if (triangle.empty()) return 0;
        vector<int> dp(triangle.size(), INT_MAX); // dp vector-reuse on every row
        // Build bottom up
        for (int i=triangle.size()-1; i>=0; i--) {
            for (int j=0; j<triangle[i].size(); j++) {
                if (i==triangle.size()-1) // The initial condition
                    dp[j]=triangle[i][j];
                else
                    dp[j]=triangle[i][j]+min(dp[j], dp[j+1]);
            }
        }
        return dp[0];
    }
};