leetcode120

Golang:

思路：这题是基础DP，想一想就出来了，但是槽点满满，题目对于相邻这个定义的解释太扯淡了。搬我的题解过来吧。

初始：
[2],
[3,4],
[6,5,7]
第一轮过后：3+2=5，4+2=6
[2],
[5,6],
[6,5,7]
第二轮过后：6+5=11，[5+5=10,5+6=11,取小值10]，7+6=13
[2],
[5,6],
[11,10,13]

代码如下：

func minimumTotal(triangle [][]int) int {
    if len(triangle)==1 {
        return triangle[0][0]
    }
    for i:=1; i<len(triangle); i++ {
        for j:=0;j<i;j++{
            temp:=triangle[i-1][j]+triangle[i][j]
            if j-1>=0 {
                temp=min(temp,triangle[i-1][j-1]+triangle[i][j])
            }
            triangle[i][j]=temp
        }
        triangle[i][i]+=triangle[i-1][i-1]
    }
    temp:=triangle[len(triangle)-1][0]
    for _,v:=range triangle[len(triangle)-1]{
        if v<temp {
            temp=v
        }
    }
    return temp
}
func min(x int,y int) int {
    if x>y {
        return y
    }else {
        return x
    }
}

有疑问加站长微信联系（非本文作者）