三角形的最小路径和

动态规划

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
}