題目: 給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。
例如:
輸入:
[
[1,2,3],
[4,5,6],
[7,8,9]
]
輸出: 21
解釋: 因?yàn)槁窂?1→2→3→6→9 的總和最小。
輸入:
[
[1,0,3],
[4,2,1],
[3,2,2]
]
輸出: 6
解釋: 因?yàn)槁窂?1→0→2→1→2 的總和最小。
解題思路
這道題題意思很好理解, 但一些實(shí)際動(dòng)手操作的話也是有點(diǎn)難度
因?yàn)橛袔讉€(gè)很難下手點(diǎn):
每行最小怎么找到?
最小路徑怎么選取?
怎么判斷處理拐點(diǎn)?
因?yàn)轭}目描述是"一條從左上角到右下角的路徑", 所以針對(duì)當(dāng)前單元格(i, j),只用考慮3種情況
左邊界單元格只能從上方單元格移來
上邊界單元格只能從左邊單元格移來
其他情況(i, j) 只能從左邊單元格(i-1, j)或上方單元格(i, j-1)移到
接下來我們做的是, 把原來數(shù)組值替換, 替換到達(dá)這里面的最小值
可以看到
i = 0, j = 0 起點(diǎn)值不變
i ≠ 0, j = 0 左邊界, cgrid[i][j] = cgrid[i-1][j] + cgrid[i][j]
i = 0, j ≠ 0 上邊界, cgrid[i][j] = cgrid[i][j-1] + cgrid[i][j]
i ≠ 0, j ≠ 0 其余情況, 我們?nèi)∽筮呉粋€(gè)單元格, 上面的單元格 兩者之中的最小值
即: cgrid[i][j] = cgrid[i-1][j] < cgrid[i][j-1] ?
cgrid[i-1][j] + cgrid[i][j] : cgrid[i][j-1] + cgrid[i][j]
func minPathSum(_ grid: [[Int]]) -> Int {
var cgrid = grid
for i in 0..<cgrid.count {
for j in 0..<cgrid[0].count {
if i == 0 && j == 0 {
continue
}else if i == 0 {
cgrid[i][j] = cgrid[i][j-1] + cgrid[i][j]
}else if j == 0 {
cgrid[i][j] = cgrid[i-1][j] + cgrid[i][j]
}else {
cgrid[i][j] = cgrid[i-1][j] < cgrid[i][j-1] ?
cgrid[i-1][j] + cgrid[i][j] : cgrid[i][j-1] + cgrid[i][j]
}
}
}
return cgrid[cgrid.count - 1][cgrid[0].count - 1]
}
題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
