120.三角形最小路径和

120.三角形最小路径和

题解

典型的动态规划问题，题解看注释即可

代码

package mainfunc 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
}