題目描述
給定一個三角形俘陷，找出自頂向下的最小路徑和极祸。每一步只能移動到下一行中相鄰的結(jié)點上。
相鄰的結(jié)點 在這里指的是 下標(biāo) 與 上一層結(jié)點下標(biāo) 相同或者等于 上一層結(jié)點下標(biāo) + 1 的兩個結(jié)點余掖。
例如鲫凶，給定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自頂向下的最小路徑和為 11（即禀崖，2 + 3 + 5 + 1 = 11）衩辟。
說明：
如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數(shù)）來解決這個問題螟炫，那么你的算法會很加分。
解題思路
從下往上遍歷一遍艺晴，每個元素取下一行兩個元素中的小值昼钻，這個思路真是太棒了，簡直完美封寞！
1.先鎖定到倒數(shù)第二行最右邊的點然评，從這里開始計算
2.計算每個店到低端的最小值，覆蓋掉triangle中的原值狈究，這一步非常重要碗淌。接下來triangle中的值就代表距離低端最近的距離。
func minimumTotal(triangle [][]int) int {
tLen:=len(triangle)
if tLen<=0{
return 0
}
for i:=tLen-2;i>=0;i--{
for j:=len(triangle[i])-1;j>=0;j--{
triangle[i][j]=triangle[i][j]+min(triangle[i+1][j],triangle[i+1][j+1])
}
}
return triangle[0][0]
}
func min(a,b int) int{
if a>b{
return b
}
return a
}
相互學(xué)習(xí)抖锥，共同進步亿眠。
