动态规划之三角形最短路径和

题目

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

思路

把三角形转换成靠左对齐的一个个子块理解
那么到第 i 层的第 j 个子块的最短路径和等于:
第 i-1 层第 j-1 个子块加第 i 层的第 j 个子块
第 i-1 层第 j 个子块加第 i 层的第 j 个子块

这两者的最小值

状态转移方程

dp[i][j] = min(dp[i-1][j-1]+dp[i-1][j])+triangle[i][j]

最终代码

func calc(triangle [][]int) int {
    length := len(triangle)
    if length < 1 {
        return 0
    }
    if length == 1 {
        return triangle[0][0]
    }
    dp := make([][]int, length)
    for i, each := range triangle {
        dp[i] = make([]int, len(each))
    }
    result := math.MaxInt32
    dp[0][0] = triangle[0][0]
    dp[1][1] = triangle[1][1] + triangle[0][0]
    dp[1][0] = triangle[1][0] + triangle[0][0]

    for i := 2; i < length; i++ {
        for j := 0; j < len(triangle[i]); j++ {
            if j == 0 {
                dp[i][j] = dp[i-1][j] + triangle[i][j]
            } else if j == (len(triangle[i]) - 1) {
                dp[i][j] = dp[i-1][j-1] + triangle[i][j]
            } else {
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
            }
        }
    }
    for _, k := range dp[length-1] {
        result = min(result, k)
    }
    return result
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}