# Leetcode 120. Triangle

Description: 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.

Link: 120. Triangle

Examples:

```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```

```class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
n = len(triangle)
if n == 0: return triangle[0][0]
dp = [[0]*i for i in range(1,n+1)]
# print(dp)
dp[0][0] = triangle[0][0]
for row in range(1, n):
for i in range(row+1):
if i == 0:
dp[row][i] = triangle[row][i] + dp[row-1][i]
elif i > 0 and i < row:
dp[row][i] = triangle[row][i] + min(dp[row-1][i-1], dp[row-1][i])
else:
dp[row][i] = triangle[row][i] + dp[row-1][i-1]
return min(dp[-1])```

Leetcode 120. Triangle

(0)
(0)

© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4