三角形最小路径和

中英题面

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

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(N2)

空间复杂度:

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]

相关推荐