159 - 120 三角形最小路径和

题目

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

例如，给定三角形：

[ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

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

解答

一开始想法是用贪心，每次都选择下一行的最小值。结果遇到了一个反例：

[[-1], [2, 3], [1, -1, -3]]，这个走-1, 3, -3是最小值-1，但如果是贪心的话，只能取到0。

动态规划：自下而上

var minimumTotal = function(triangle) {
  for (let i = triangle.length - 2; i >= 0; i--) {
    for (let j = 0; j < triangle[i].length; j++) {
      triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1])
    }
  }
  return triangle[0][0]
};

Runtime: 56 ms, faster than 73.89% of JavaScript online submissions for Triangle.

Memory Usage: 34.9 MB, less than 100.00% of JavaScript online submissions for Triangle.

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

Runtime: 52 ms, faster than 99.32% of Python3 online submissions for Triangle.

Memory Usage: 13.6 MB, less than 33.33% of Python3 online submissions for Triangle.

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func minimumTotal(triangle [][]int) int {
    for i := len(triangle) - 2; i >= 0; i-- {
        for j := 0; j < len(triangle[i]); j++ {
            triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])
        }
    }
    return triangle[0][0]
}

Runtime: 4 ms, faster than 94.83% of Go online submissions for Triangle.

Memory Usage: 3.1 MB, less than 100.00% of Go online submissions for Triangle.