64. 最小路径和

题意

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

路径上的数字总和为最小。

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

难度

中等

示例

示例 1：

1669688825007-316d08e6-c066-479e-9dff-3ff4dcd97ad2.jpeg

输入：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

分析

本题还是可以用 动态规划 来解决，因为这题和前面两题—— 062.不同路径、063.不同路

径 II 有一个共同之处，每个位置都只能由它的上方或者是左边转移而来。

同样，我们还是利用 f[i][j]来表示走到第 i 行第 j 列最少的数字总和。

基于这样子的思想我们可以写出如下的动态转移方程：

$ f(i,j) ={

.$

依照该动态转移方程，我们可以写出如下的代码。

class Solution {

public int minPathSum(int[][] grid) {

for(int i = 0;i < grid.length;i++) {

for (int j = 0; j < grid[0].length; 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] += Math.min(grid[i][j - 1], grid[i - 1][j]);}

}

}

return grid[grid.length - 1][grid[0].length - 1];

}

}

代码中直接利用了 grid[][]来替代 f[][]，来节省空间。

最终的时间复杂度为$ O(nm) ，空 间 复 杂 度 也 为 O(nm) $。

1669688833282-7bd52084-5869-4e04-8213-1f5b7a73b7f7.png

总结

这类在网格图上行走，并且要求最小值/最大值的题目，通常可以利用 动态规划 来解决，

我们首先将该题的 状态（本题中即网格图的位置） 提取出来，再观察这个状态是由那些

状态转移而来的，是怎么转移的，从而总结出动态转移方程，最后便可以写出代码了。

力扣链接：https://leetcode.cn/problems/minimum-path-sum/