# LeetCode 120. Triangle

## Description

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 = [,[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.length == 1`
• `triangle[i].length == triangle[i - 1].length + 1`
• `-104 <= triangle[i][j] <= 104`

Follow up: Could you do this using only `O(n)` extra space, where `n` is the total number of rows in the triangle?

## Explanation

Track the minimum path sum at each element. At each row, the j th element’s minimum path sum could either get from the previous row j – 1 element or j – 1 element.

## Python Solution

``````class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
dp = [[] for i in range(len(triangle))]

for i in range(len(triangle)):
if i == 0:
dp[i].append(triangle[i])
else:
for j in range(len(triangle[i])):
if j == 0:
dp[i].append(dp[i - 1][j] + triangle[i][j])
elif j == len(triangle[i]) - 1:
dp[i].append(dp[i - 1][j - 1] + triangle[i][j])
else:
dp[i].append(min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j])

min_path_sum = sys.maxsize

for path_sum in dp[-1]:
min_path_sum = min(min_path_sum, path_sum)

return min_path_sum

``````
• Time Complexity: O(N^2).
• Space Complexity: O(N^2).