Leetcode Golang 120. Triangle.go

anakinsun

发布于 2019-04-12 10:21:12

3280

发布于 2019-04-12 10:21:12

文章被收录于专栏：学习日记学习日记

思路

dp算法

dp数组保存当前行获得的最小值

从下往上转移

初始化为最后一行的值

code

func minimumTotal(triangle [][]int) int {
	l := len(triangle)
	if l == 0 {
		return 0
	}
	if l == 1 {
		return triangle[0][0]
	}
	dp := make([]int, l)
	//dp数组初始化成最后一行的值
	for i := 0; i < l; i++ {
		dp[i] = triangle[l-1][i]
	}
	for i := l - 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(x, y int) int {
	if x > y {
		return y
	}
	return x

}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019年04月02日，如有侵权请联系 cloudcommunity@tencent.com 删除

code