# # 【LeetCode】120. Triangle 解题报告（Python）

## # 题目描述：

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

``````[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
``````

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

## # 解题方法

``````minpath[k][i] = min( minpath[k+1][i], minpath[k+1][i+1]) + triangle[k][i];
``````

``````For the kth level:
minpath[i] = min( minpath[i], minpath[i+1]) + triangle[k][i];
``````

``````class Solution(object):
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
n = len(triangle)
dp = triangle[-1]
for layer in range(n - 2, -1, -1):
for i in range(layer + 1):
dp[i] = min(dp[i], dp[i + 1]) + triangle[layer][i]
return dp[0]
``````

https://leetcode.com/problems/triangle/discuss/38730/DP-Solution-for-Triangle

## # 日期

2018 年 9 月 27 日 —— 国庆9天长假就要开始了！