64. 最小路径和 好

64. 最小路径和

给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

复杂度分析

• 时间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。需要对整个网格遍历一次，计算dp 的每个元素的值。
  

• 空间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。创建一个二维数组 dp，和网格大小相同。
  空间复杂度可以优化，例如每次只存储上一行的 dp 值，则可以将空间复杂度优化到 O(n)。
  ```go //二维法 func minPathSum(grid [][]int) int { if len(grid) == 0 || len(grid[0]) == 0 {

    return 0

  }

  m , n := len(grid), len(grid[0]) dp := make([][]int, m) //1，定义dp含义

for i := 0; i < m; i++ {
    dp[i] = make([]int, n)         //2，初始化dp【i】
}
dp[0][0] = grid[0][0]                   //权重初值, 需要初始化完成才能赋值

for i := 1; i < m; i++ {                //定义矩阵最左边的边界
    dp[i][0] = dp[i-1][0] + grid[i][0]
}
for j := 1; j < n; j++ {                //定义矩阵最上边的边界
    dp[0][j] = dp[0][j-1] + grid[0][j]
}

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(x,y int) int { if x < y { return x } return y }

```go
//一维优化后
func minPathSum(grid [][]int) int {
    n := len(grid[0])
    dp := make([]int, n)

    for i := range grid {
        dp[0] += grid[i][0]

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

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}