Skip to main content

64. Minimum Path Sum

分析

用 -1 的时候注意边界
典型dp问题

题解

func minPathSum(grid [][]int) int {
m, n := len(grid), len(grid[0])
dp := make([][]int, m)
for i := 0; i < m; i++ {
dp[i] = make([]int, n)
}
dp[0][0] = grid[0][0]
// 第一行 所有列
for i := 1; i < n; i++ {
dp[0][i] = dp[0][i-1] + grid[0][i]
}
// 第一列 所有行
for i := 1; i < m; i++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}

for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
}
}

return dp[m-1][n-1]
}

func min(a, b int ) int {
if a < b {
return a
}
return b
}