LeetCode-热题100：64. 最小路径和

题目描述

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

**说明：**每次只能向下或者向右移动一步。

示例 1：

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

示例 2：

输入： grid = [[1,2,3],[4,5,6]]
输出： 12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

代码及注释

func minPathSum(grid [][]int) int {
    // 遍历二维网格
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            // 如果是起点，跳过
            if i == 0 && j == 0 {
                continue
            } 
            // 对于第一行，只能从左边的格子过来
            if i == 0 {
                grid[i][j] += grid[i][j - 1]
            } else if j == 0 {
                // 对于第一列，只能从上方的格子过来
                grid[i][j] += grid[i - 1][j]
            } else {
                // 对于其他格子，路径和为上方格子和左方格子中较小的路径和加上当前格子的值
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
            }
        }
    }
    // 返回右下角格子的最小路径和
    return grid[len(grid) - 1][len(grid[0]) - 1]
}

// 辅助函数，返回两个数中的较小值
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

代码解释

1. 遍历二维网格:

   for i := 0; i < len(grid); i++ {
       for j := 0; j < len(grid[0]); j++ {
           // 如果是起点，跳过
           if i == 0 && j == 0 {
               continue
           } 
           // 对于第一行，只能从左边的格子过来
           if i == 0 {
               grid[i][j] += grid[i][j - 1]
           } else if j == 0 {
               // 对于第一列，只能从上方的格子过来
               grid[i][j] += grid[i - 1][j]
           } else {
               // 对于其他格子，路径和为上方格子和左方格子中较小的路径和加上当前格子的值
               grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
           }
       }
   }
   

   • 使用两层循环遍历二维网格，计算每个格子的最小路径和。
   • 对于第一行和第一列的格子，只能从一个方向过来，所以只需加上一个方向的值。
   • 对于其他格子，最小路径和为上方格子和左方格子中较小的路径和加上当前格子的值。

2. 返回结果:

   return grid[len(grid) - 1][len(grid[0]) - 1]
   

   • 返回右下角格子的最小路径和，即为从左上角到右下角的最小路径和。

3. 辅助函数:

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

   • 辅助函数 min 用于返回两个数中的较小值。

这个动态规划的解法时间复杂度为 O(m × n)，空间复杂度为 O(1)，因为我们直接修改了输入的二维网格。