# 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.

# Solution

Approach 1: DP -- either from top to bottom, or from bottom to top.

# Code (Python)

Approach 1:

    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # bottom up
        if not triangle:
            return 0
        result = triangle[-1]
        for row_num in range(len(triangle) - 2, -1, -1):
            for i in range(len(triangle[row_num])):
                result[i] = min(result[i], result[i+1]) + triangle[row_num][i]
        return result[0]
    
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # top-down
        if not triangle:
            return 0
        for row in triangle:
            if len(row) == 1:
                totals = row
                continue
            for i in range(len(row) - 1, -1, -1):
                item = row[i]
                if i == 0:
                    totals[0] += item
                elif i == len(row) - 1:
                    totals.append(totals[i-1] + item)
                else:
                    totals[i] = min(totals[i-1], totals[i]) + item
        return min(totals)

# Code (C++)

Approach 1:

// DP.
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int rowSize = triangle.size();
        if (rowSize == 0)
            return 0;
        int maxColSize = triangle[rowSize-1].size();
        int minSums[maxColSize+1] = {0};
        for (int i = rowSize - 1; i >= 0; --i)
        {
            for (int j = 0; j < triangle[i].size(); ++j)
            {
                if (minSums[j] <= minSums[j+1])
                    minSums[j] += triangle[i][j];
                else
                    minSums[j] = triangle[i][j] + minSums[j+1];
            }       
        }
        return minSums[0];
    }
};