LeetCode 64「最小路径和」的 Go 实现同样提供原地修改和一维滚动数组两个版本。原地修改版O(1) 额外空间funcminPathSum(grid[][]int)int{m,n:len(grid),len(grid[0])// 第一行只能从左向右累加forj:1;jn;j{grid[0][j]grid[0][j-1]}// 第一列只能从上向下累加fori:1;im;i{grid[i][0]grid[i-1][0]}fori:1;im;i{forj:1;jn;j{grid[i][j]min(grid[i-1][j],grid[i][j-1])}}returngrid[m-1][n-1]}一维滚动数组版不修改输入funcminPathSum(grid[][]int)int{n:len(grid[0])dp:make([]int,n)forj:rangedp{dp[j]math.MaxInt32}dp[0]0for_,row:rangegrid{dp[0]row[0]forj:1;jn;j{dp[j]row[j]min(dp[j],dp[j-1])}}returndp[n-1]}复杂度时间 O(m×n)原地版额外空间 O(1)滚动数组版 O(n)。Go 细节Go 的切片是引用传递minPathSum会直接修改调用方传入的grid与 Python/Rust 一致LeetCode 判题不受影响。如需保护输入滚动数组版本不修改gridmin内置函数需 Go 1.21低版本用if a b { return a }或math.Min注意后者是float64 Kimi LeetCode 64. 最小路径和 Golang实现
LeetCode 64「最小路径和」的 Go 实现同样提供原地修改和一维滚动数组两个版本。原地修改版O(1) 额外空间funcminPathSum(grid[][]int)int{m,n:len(grid),len(grid[0])// 第一行只能从左向右累加forj:1;jn;j{grid[0][j]grid[0][j-1]}// 第一列只能从上向下累加fori:1;im;i{grid[i][0]grid[i-1][0]}fori:1;im;i{forj:1;jn;j{grid[i][j]min(grid[i-1][j],grid[i][j-1])}}returngrid[m-1][n-1]}一维滚动数组版不修改输入funcminPathSum(grid[][]int)int{n:len(grid[0])dp:make([]int,n)forj:rangedp{dp[j]math.MaxInt32}dp[0]0for_,row:rangegrid{dp[0]row[0]forj:1;jn;j{dp[j]row[j]min(dp[j],dp[j-1])}}returndp[n-1]}复杂度时间 O(m×n)原地版额外空间 O(1)滚动数组版 O(n)。Go 细节Go 的切片是引用传递minPathSum会直接修改调用方传入的grid与 Python/Rust 一致LeetCode 判题不受影响。如需保护输入滚动数组版本不修改gridmin内置函数需 Go 1.21低版本用if a b { return a }或math.Min注意后者是float64