题目

给定一个三角形 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

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

注意：本题与主站 120 题相同：

解题思路分析

1、动态规划；时间复杂度O(n^2)，空间复杂度O(n^2)

func minimumTotal(triangle [][]int) int {
   n := len(triangle)
   dp := make([][]int, n)
   for i := 0; i < n; i++ {
      dp[i] = make([]int, n)
   }
   dp[0][0] = triangle[0][0]
   for i := 1; i < n; i++ {
      dp[i][0] = dp[i-1][0] + triangle[i][0]
      for j := 1; j < i; j++ {
         dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
      }
      dp[i][i] = dp[i-1][i-1] + triangle[i][i]
   }
   res := dp[n-1][0]
   for i := 1; i < n; i++ {
      res = min(res, dp[n-1][i])
   }
   return res
}

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

2、动态规划；时间复杂度O(n^2)，空间复杂度O(n)

func minimumTotal(triangle [][]int) int {
   n := len(triangle)
   dp := [2][]int{}
   for i := 0; i < 2; i++ {
      dp[i] = make([]int, n)
   }
   dp[0][0] = triangle[0][0]
   for i := 1; i < n; i++ {
      cur := i % 2
      prev := 1 - cur
      dp[cur][0] = dp[prev][0] + triangle[i][0]
      for j := 1; j < i; j++ {
         dp[cur][j] = min(dp[prev][j-1], dp[prev][j]) + triangle[i][j]
      }
      dp[cur][i] = dp[prev][i-1] + triangle[i][i]
   }
   res := dp[(n-1)%2][0]
   for i := 1; i < n; i++ {
      res = min(res, dp[(n-1)%2][i])
   }
   return res
}

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

3、动态规划；时间复杂度O(n^2)，空间复杂度O(n)

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] = dp[0] + triangle[i][0]
   }
   res := dp[0]
   for i := 1; i < n; i++ {
      res = min(res, dp[i])
   }
   return res
}

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

4、遍历；时间复杂度O(n^2)，空间复杂度O(1)

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

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

5、递归；时间复杂度O(n^2)，空间复杂度O(n^2)

var dp [][]int

func minimumTotal(triangle [][]int) int {
   dp = make([][]int, len(triangle))
   for i := 0; i < len(triangle); i++ {
      dp[i] = make([]int, len(triangle))
   }
   return dfs(triangle, 0, 0)
}

func dfs(triangle [][]int, i, j int) int {
   if i == len(triangle) {
      return 0
   }
   if dp[i][j] != 0 {
      return dp[i][j]
   }
   dp[i][j] = min(dfs(triangle, i+1, j), dfs(triangle, i+1, j+1)) + triangle[i][j]
   return dp[i][j]
}

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

总结

Medium题目，题目同leetcode 120.三角形最小路径和