# 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];
}
};