LeetCode: 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.

---

We can create an array of the same size as the last row of the triangle, so the minimum sum to each element in the row is the minimum sum from its above left and above right.

C++ Code:

/*
 * func: minimum_path_sum
 * goal: find the minimum path sum from top to bottom.
 * @param triangle: input number triangle
 * return: minimum sum
 */
int minimum_path_sum(vector<vector<int> > &triangle){
    if(triangle.size() == 0){
        return 0;
    }
    vector<int> sum(triangle.size(), 0);
    sum[0] = triangle[0][0];
    for(int i=1; i<triangle.size(); ++i){
        vector<int> prev_sum = sum;
        for(int j = 0; j < triangle[i].size(); ++j){
            if(j == 0){
                sum[j] = prev_sum[j] + triangle[i][j];
            }else if(j == triangle[i].size()-1){
                sum[j] = prev_sum[j-1] + triangle[i][j];
            }else{
                sum[j] = min(prev_sum[j-1], prev_sum[j]) + triangle[i][j];
            }
        }
    }
    
    int min_sum = sum[0];
    for(const int &it : sum){
        min_sum = std::min(it, min_sum);
    }
    
    return min_sum;
}

Python Code:

# func: find the minimum path sum from top to bottom
# @param triangle: input triangle
# @return: minimum sum
def minimum_path_sum(triangle):
    if not triangle:
        return 0
    
    #Compute the sum bottom up
    prev_sum_list = triangle[-1]
    for i in xrange(2, len(triangle)+1):
        curr_sum_list = []
        for j in xrange(len(triangle[-i])):
            curr_sum_list += [triangle[-i][j] + min(prev_sum_list[j], prev_sum_list[j+1])]

        prev_sum_list = curr_sum_list

    return prev_sum_list[0]