Algorithm
Problem Nmae: 120. Triangle
problem Link: https://leetcode.com/problems/triangle/
Given a
triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
Example 1:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11 Explanation: The triangle looks like: 2 3 4 6 5 7 4 1 8 3 The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
Example 2:
Input: triangle = [[-10]] Output: -10
Constraints:
1 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int minimumTotal(int** triangle, int triangleRowSize, int *triangleColSizes) {
int *x;
int i, j, k;
if (triangleRowSize == 1) return triangle[0][0];
x = malloc(triangleRowSize * sizeof(int));
if (!x) return 0;
for (i = triangleRowSize - 1; i >= 0 ; i --) {
for (j = 0; j < triangleColSizes[i]; j ++) {
if (i == triangleRowSize - 1) {
k = 0;
} else if (x[j] < x[j + 1]) {
k = x[j];
} else {
k = x[j + 1];
}
k += triangle[i][j];
x[j] = k;
}
}
free(x);
return k;
}
Input
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output
11
#2 Code Example with C++ Programming
Code -
C++ Programming
// Bottom-up
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<int>dp(n + 1);
for(int i = n - 1; i >= 0; i--)
for(int j = 0; j < = i; j++)
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
return dp[0];
}
};
// Top-down
class Solution {
public:
int minimumTotal(vector < vector<int>>& triangle) {
int n = triangle.size();
vector<int>dp(n);
for(int i = 0; i < n; i++){
if(i != 0) dp[i] = dp[i - 1] + triangle[i][i];
for(int j = i - 1; j > 0; j--)
dp[j] = triangle[i][j] + min(dp[j], dp[j - 1]);
dp[0] = dp[0] + triangle[i][0];
}
return *min_element(dp.begin(), dp.end());
}
};
Input
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output
11
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int minimumTotal(List dp = new HashMap<>();
return minimumTotalHelper(triangle, dp, 0, 0);
}
private int minimumTotalHelper(List < List dp, int row, int col) {
String key = row + "|" + col;
if (dp.containsKey(key)) {
return dp.get(key);
}
int path = triangle.get(row).get(col);
if (row < triangle.size() - 1) {
path += Math.min(minimumTotalHelper(triangle, dp, row + 1, col), minimumTotalHelper(triangle, dp, row + 1, col + 1));
}
dp.put(key, path);
return dp.get(key);
}
}
Input
triangle = [[-10]]
Output
-10
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const minimumTotal = function(triangle) {
const n = triangle.length;
for (let i = n - 2; i >= 0; i--) {
for (let j = 0; j < n; j++) {
let self = triangle[i][j]; //获取第（i+1）行（j+1）个数字
let res = Math.min(
triangle[i + 1][j] + self,
triangle[i + 1][j + 1] + self
); //得到这一行与下一行相邻数的和的最小值
triangle[i][j] = res; //更新第（i+1）行第（j+1）个数字
}
}
return triangle[0][0];
};
Input
triangle = [[-10]]
Output
-10
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
prev = None
for tri in triangle:
if prev:
for i, num in enumerate(tri):
if i >= len(prev): tri[i] += prev[i - 1]
elif i == 0: tri[i] += prev[0]
else: tri[i] += min(prev[i - 1], prev[i])
prev = tri
return min(triangle[-1])
Input
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output
11
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _120_Triangle
{
public int MinimumTotal(IList < IList<int>> triangle)
{
if (triangle.Count == 0) return 0;
for (int i = 1; i < triangle.Count; i++)
for (int j = 0; j < = i; j++)
if (j == 0)
triangle[i][j] += triangle[i - 1][j];
else if (j == i)
triangle[i][j] += triangle[i - 1][j - 1];
else
triangle[i][j] += Math.Min(triangle[i - 1][j], triangle[i - 1][j - 1]);
return triangle.Last().Min();
}
}
}
Input
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output
11