Re: [閒聊] 每日leetcode
邊聽咩唱歌，編寫leestcode
快唱完了，剛好想到要怎麼寫
1289. Minimum Falling Path Sum II
有一個n*n的matrix，請回傳最短落下路徑
最短落下路徑的限制：相鄰兩列的元素其行不能相等
思路：
因為行不能相等，所以要維持2條路徑
這兩條路徑的最後元素不能在同一行，在這個限制下這兩條路徑的值要是最小以及次小
到i-1列的最小值是在j行，那到ｉ列的最小、次小值
一定是由到i-1列的最小值與非ｊ行元素相加、到i-1列次小值與ｊ行元素相加
這兩種可能
就這樣就可以得到答案了
golang code:
func minFallingPathSum(grid [][]int) int {
rec:=[]int{0,0,-1}
for i:=0;i<len(grid);i++{
var value int
temp:=[]int{math.MaxInt,math.MaxInt,-1}
for j:=0;j<len(grid[0]);j++{
if j!=rec[2]{
value=rec[0]+grid[i][j]
}else{
value=rec[1]+grid[i][j]
}
if value<=temp[0]{
temp[1]=temp[0]
temp[0]=value
temp[2]=j
}else if value<temp[1]{
temp[1]=value
}
}
rec=temp
}
return rec[0]
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.75.239.113 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714141594.A.B18.html
推
04/26 22:33,
1月前
, 1F
04/26 22:33, 1F
討論串 (同標題文章)