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

120.三角形最小路径和

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
}