跳转至

LeetCode: 120. 三角形最小路径和

1、题目描述

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

​ 例如，给定三角形：

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

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

说明：

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

2、解题思路

​ 通过上面的描述，第一时间能够想到的就是动态规划，这个动态规划与一般的不一样，之前做的题目的状态都是某个节点的状态依赖于其他的一个或几个节点，但这里不太一样的就是，我们要将每一行看作是一个状态，上一行依赖于下一行

​ 因此，我们设计一个缓冲数组即可，长度为n，从下向上进行计算，左后一行比较特殊，直接赋值即可

倒数第二行，每一个数字都是当前数字和下面一行的数字之和中更小的那个

举个例子，

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

一开始，缓冲数组赋值为最后一行的值

[4,1,8,3]

然后，计算前面一行的值，这时候，需要考虑一下下面一行的相邻节点的值

首先是6，他的相邻节点是4，1
和值为10，7，我们取最小的，7，放到开头
[7,1,8,3]
然后是5，他的相邻节点是1，8
和值是6，13，取最小值6
[7,6,8,3]
然后是7，他的相邻节点是8，3
和值为15，10，取最小值10
[7,6,10,3]
这样，第三行的数据就处理完了，以此类推，处理到最后的第一行的时候，位于行首的元素就是我们所要的答案

class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        length = len(triangle)
        if length == 1:
            return triangle[0][0]

        line = triangle[-1][:]

        for i in range(length - 2, -1, -1):
            for j in range(i + 1):
                line[j] = min(triangle[i][j] + line[j], triangle[i][j] + line[j+1])

        return line[0]