leetcode 120. 三角形最小路径和

题目描述

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


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

自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

题解

自底向上依次选取最小值相加

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
func minimumTotal(triangle [][]int) int {
for i := len(triangle)-2; i >= 0; i-- {
for j := 0; j < len(triangle[i]); j++ {
if triangle[i+1][j] > triangle[i+1][j+1] {
triangle[i][j] += triangle[i+1][j+1]
} else {
triangle[i][j] += triangle[i+1][j]
}
}
}
return triangle[0][0]
}