三角形最小路径和

中英题面

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

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

例如，给定三角形：

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

自顶向下的最小路径和为11（即，2+3+5+1= 11）。

For example, given the following triangle

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

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

说明：

如果你可以只使用O(n)的额外空间（n为三角形的总行数）来解决这个问题，那么你的算法会很加分。

Note:

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

算法

直接借用原来的数组，从三角形底部反着迭代算就行了。

转移方程：

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

答案：

triangle[0][0]

时间复杂度：

O(N²)

空间复杂度：

O(1)

代码

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