120. 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 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）。

image.png

  1. //二维，时空都是On^2
  2. func minimumTotal(triangle [][]int) int {
  3.     n := len(triangle)
  4.     dp := make([][]int, n)                  //1，定义dp
  6.     for i := 0; i <n; i++ {
  7.         dp[i] = make([]int, n)              //2, 初始化dp[i]
  8.     }
  9.     dp[0][0] = triangle[0][0]               //3，权重初值
  11.     for i := 1; i < n; i++ {
  12.         dp[i][0] = dp[i - 1][0] + triangle[i][0]
  13.         for j := 1; j < i; j++ {                    //核心，函数=上一层的左一个 或者本身
  14.             dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]    
  15.         }
  16.         dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]   //最后一层，因为j=i,上面只求到倒数第二层
  17.     }
  19.     //res := n + 1        //居然不行？
  20.     res := math.MaxInt32            //取个最大值呗
  21.     for i:=0; i<n; i++ {
  22.         res = min(res, dp[n-1][i])              //三角形最右侧情况
  23.     }
  25.     return res
  26. }
  28. func min(x, y int) int {
  29.     if x < y {
  30.         return x
  31.     }
  32.     return y
  33. }
//一维,   时间On^2，空间On
func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    dp := make([]int, n)

    dp[0] = triangle[0][0]

    for i := 1; i < n; i++ {
        dp[i] = dp[i - 1] + triangle[i][i]
        for j := i - 1; j > 0; j-- {
            dp[j] = min(dp[j - 1], dp[j]) + triangle[i][j]
        }
        dp[0] += triangle[i][0]
    }

    res := math.MaxInt32
    for i := 0; i < n; i++ {
        res = min(res, dp[i])
    }

    return res
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

解题思路

从下往上遍历一遍，每个元素取下一行两个元素中的小值，这个思路真是太棒了，简直完美！

//二维
func minimumTotal(triangle [][]int) int {
    h := len(triangle)
    dp := make([][]int, h)

    for i := range dp {
        dp[i] = make([]int, len(triangle[i]))
    }

    for i := h - 1; i >= 0; i-- {
        for j := 0; j < len(triangle[i]); j++ {
            if i == h-1 {
                dp[i][j] = triangle[i][j]
            } else {
                dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
            }
        }
    }

    return dp[0][0]
}

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

//一维
func minimumTotal(triangle [][]int) int {
    bottom := triangle[len(triangle)-1]
    dp := make([]int, len(bottom))
    for i := range dp {
        dp[i] = bottom[i]
    }

    for i := len(dp) - 2; i >= 0; i-- {
        for j := 0; j < len(triangle[i]); j++ {
            dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
        }
    }
    return dp[0]
}

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