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

---

解题分析及思路：

由于只能向下或者向右移动，所以对于所在位置(i,j),那么他的上一步有两种可能：

• 如果向下走一步，那么会从 (i−1,j) 走过来；
• 如果向右走一步，那么会从(i,j−1)走过来。

所以在位置(i,j)，路过路径上的最小值为走到位置(i-1,j)或走到位置(i,j-1)之和，那么对应的状态转移方程为：f(i,j)=f(i,j)+min(f(i−1,j),f(i,j−1))

那么对应动态规划解法：

1. 定义状态： 在这个问题中，状态可以定义为到达每个位置时的不同路径数量。我们使用二维数组 dp 表示状态，其中 dp[i][j] 表示到达网格位置 (i, j) 时路过的所有地方的数字总和。

2. 找到状态转移方程： 每次只能向下或者向右移动一步，因此到达当前位置 (i, j) 的数字之和等于到达上方位置 (i-1, j) 和到达左方位置 (i, j-1) 的数字的最小值与当前位置的数组之和。状态转移方程可以表示为：

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

3. 初始化： 在初始化阶段，我们遍历第一行和第一列，将每个位置的数字更新为该位置前的数字之和，因为规定只能向下或向右移动，所以沿着第一行和第一列的路径都只有一种。

4. 递推求解： 通过嵌套循环遍历整个二维数组，根据状态转移方程计算到达每个位置的数字之和。

5. 计算最终结果： 最终结果即为到达右下角位置 (m-1, n-1) 时的数字之和。

优化：由于当前位置只与上方和左方位置有关，并且后续不再使用原数据，所以完全可以在原数组上进行修改。

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

复杂度：

• 时间复杂度：O(M*N)，其中 M 为 m 的值，N 为 n 的值。
• 空间复杂度：O(1)，原地修改。

执行结果：

• 执行耗时:3 ms,击败了93.92% 的Go用户
• 内存消耗:3.3 MB,击败了94.48% 的Go用户