动态规划
代码语言：javascript复制package main
import (
"fmt"
"math"
)
//给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
//
//相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 1 的两个结点。
//
//
//
//例如，给定三角形：
//
//[
//[2],
//[3,4],
//[6,5,7],
//[4,1,8,3]
//]
//自顶向下的最小路径和为 11（即，2 3 5 1 = 11）。
func main() {
fmt.Println(minimumTotal([][]int{
{2},
{3,4},
{6,5,7},
{4,1,8,3},
}))
}
//走到[i,j]肯定是从上一层的[i-1,j],或者是[i-1,j-1]来的,那么走到要走到[i,j]最小，那肯定是min([i-1,j],[i-1,j-1])，层层走下去
func minimumTotal(triangle [][]int) int {
addrTime := make([][]int, len(triangle))
for i := 0; i < len(triangle); i {
addrTime[i] = make([]int, len(triangle))
}
addrTime[0][0] = triangle[0][0]
for i := 1; i < len(triangle); i {
addrTime[i][0] = addrTime[i-1][0] triangle[i][0]
for j := 1; j < i; j {
addrTime[i][j] = min(addrTime[i-1][j], addrTime[i-1][j-1]) triangle[i][j]
}
addrTime[i][i] = addrTime[i-1][i-1] triangle[i][i]
}
result := math.MaxInt32
for i := 0; i < len(triangle); i {
result = min(addrTime[len(triangle)-1][i], result)
}
return result
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
