120_triangle

120. 三角形最小路径和 中等

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -104 <= triangle[i][j] <= 104

进阶：

• 你可以只使用 0(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

代码参考：

package main

import "fmt"

func main() {
    triangle := [][]int{
        {2},
        {3, 4},
        {6, 5, 7},
        {4, 1, 8, 3},

        // {-1},
        // {2, 3},
        // {1, -1, -1},
    }
    fmt.Println(minimumTotal(triangle)) // 2 3 5 1
}

// 和 64 题最小路径和很像，都是用简单的动态规划实现
func minimumTotal(triangle [][]int) int {
    r := len(triangle)
    if r <= 0 {
        return 0
    }

    // 向下构建
    steps := make([][]int, r)
    for i := range triangle {
        steps[i] = make([]int, i+1)
    }
    copy(steps, triangle)

    for i := 1; i < r; i++ {
        for j := 0; j <= i; j++ { // 第 N 行有 N 个元素
            steps[i][j] += min(steps[i-1], j)
        }
    }

    minStep := steps[r-1][0]
    for _, step := range steps[r-1] {
        if minStep > step {
            minStep = step
        }
    }
    return minStep
}

// 获取某行指定位置及其左右的最小值
func min(nums []int, c int) (minNum int) {
    n := len(nums)
    l, mid := c-1, c

    inited := false
    if 0 <= l && l <= n-1 {
        inited = true
        minNum = nums[l]
    }
    if 0 <= mid && mid <= n-1 {
        if inited {
            if minNum > nums[mid] {
                minNum = nums[mid]
            }
        } else {
            inited = true
            minNum = nums[mid]
        }
    }
    return
}