golang力扣leetcode 120.三角形最小路径和

package main
func minimumTotal1(triangle [][]int) int { //自顶向下
  dp := make([][]int, len(triangle))
  for i := 0; i < len(triangle); i++ {
    dp[i] = make([]int, len(triangle[i]))
    copy(dp[i], triangle[i])
  }
  for i := 1; i < len(triangle); 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])-1 { //这一层的最后一个数字，只会是上一层的最后一个数字
        dp[i][j] = dp[i-1][j-1] + triangle[i][j]
      } else { //中间的数字有2种走法
        dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
      }
    }
  }
  result := dp[len(triangle)-2][0]
  for i := 1; i < len(dp[len(triangle)-2]); i++ {
    result = min(result, dp[len(triangle)-2][i])
  }
  return result
}
func minimumTotal2(triangle [][]int) int { //自下而上
  dp := make([][]int, len(triangle))
  for i := 0; i < len(triangle); i++ {
    dp[i] = make([]int, len(triangle[i]))
    copy(dp[i], triangle[i])
  }
  for i := len(triangle) - 2; i >= 0; i-- {
    for j := 0; j < len(triangle[i]); j++ {
      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
}