## Algorithm

Problem Nmae: 120. 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 <= 200`
• `triangle[0].length == 1`
• `triangle[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;
}
``````
Copy The Code &

Input

cmd
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

Output

cmd
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());
}
};
``````
Copy The Code &

Input

cmd
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

Output

cmd
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);
}
}
``````
Copy The Code &

Input

cmd
triangle = [[-10]]

Output

cmd
-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];
};
``````
Copy The Code &

Input

cmd
triangle = [[-10]]

Output

cmd
-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])
``````
Copy The Code &

Input

cmd
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

Output

cmd
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();
}
}
}
``````
Copy The Code &

Input

cmd
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

Output

cmd
11