LeetCode 120. Triangle minimum path sum

## Title address (120. The minimum path of a triangle and )

https://leetcode-cn.com/problems/triangle/

## Title Description

Given a triangle triangle , Find the smallest sum from the top down .

Each step can only move to adjacent nodes in the next row . Adjacent nodes What I mean here is Subscript And The upper node subscript Equal to or equal to The upper node subscript + 1 Two nodes of . in other words , If it is in the subscript of the current line i , So the next step is to move to the subscript of the next line i or i + 1 .

```

Example 1：

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

Output ：11

explain ： As shown in the diagram below ：

2

3 4

6 5 7

4 1 8 3

The minimum path sum from the top down is zero  11（ namely ,2 + 3 + 5 + 1 = 11）.

Example 2：

Input ：triangle = [[-10]]

Output ：-10

```

Tips ：

1 <= triangle.length <= 200

triangle[0].length == 1

triangle[i].length == triangle[i - 1].length + 1

-104 <= triangle[i][j] <= 104

 

Advanced ：

You can just use O(n)  Extra space （n Is the total number of rows of the triangle ） To solve this problem ？

## Ideas

DP planning , Store each set of states in DP In an array , The method of optimizing space is to put 【-2】 Remove the array , Save only 【-1】 And now traverse the array for reduction

## Code

- Language support ：Python3

Python3 Code:

```python

class Solution:

def minimumTotal(self, triangle: List[List[int]]) -> int:

cengNum = len(triangle)

dp = []

for i in range(cengNum):

dp.append([0]*len(triangle[i]))

dp[0][0] = triangle[0][0]

for i in range(1,cengNum):

cengList = triangle[i]

for j,val in enumerate(cengList):

## Triangular edge

if j == 0:

dp[i][j] = dp[i-1][j]+val

elif j == len(cengList)-1:

dp[i][j] = dp[i-1][j-1]+val

else:# The center position adopts min count

dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])+val

res = min(dp[-1])

# print(dp)

return res

if __name__ == '__main__':

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

# triangle = [[-10]]

res = Solution().minimumTotal(triangle)

print(res)

```

** Complexity analysis **

Make n Is array length .

- Time complexity ：$O(n^2)$

- Spatial complexity ：$O(n^2)$