一、题目描述

给定一个包含非负整数的 m * 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] <= 100

题目链接：https://leetcode.cn/problems/minimum-path-sum

二、解题思路

我们将经过的格子的重量叠加到当前到的格子上，就是当前路径的和。

从左上角到右下角的路径，每走一步只能是向右走或者向下走，因此到达某一个格子只会是 从上面来 的或者 从左边来 的。

因此要找最小路径的话，我们在叠加当前格子时，要选择已经走过的代价比较小的那条路：选择上面或者左边格子比较小的那一个。

也有例外：第一横排只能是左边来的，第一竖列只能是上面来的。

我们可以一排一排遍历：

第一排：grid[i][j] = grid[i][j] + grid[i][j-1]
第一列：grid[i][j] = grid[i][j] + grid[i-1][j]
其他位置：

grid[i][j] = grid[i][j] + min(grid[i-1][j],grid[i][j-1])

三、我的题解

Go 语言代码：

func minPathSum(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    for i:=0; i<m;i++{
        for j:=0; j<n;j++{
            if i==0 && j==0{
                continue
            }else if i==0{
                grid[i][j] = grid[i][j] + grid[i][j-1]
            }else if j==0{
                grid[i][j] = grid[i][j] + grid[i-1][j]
            }else{
                grid[i][j] = grid[i][j] + min(grid[i-1][j],grid[i][j-1])
            }
        }
    }
    return grid[m-1][n-1]
}

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