64. 最小路径和

不念不忘少年蓝@ 2024-03-26 16:45 71阅读 0赞

### 64. 最小路径和 ###

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

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

##### 示例 1： #####

![在这里插入图片描述][6d57f73ce4194643b1946fdad3401423.png]

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

#### 思路：(动态规划) ####

由于每次只能向下或者向右移动，所以到达任意一个位置，不是从上面到达就是从左边到达，从而比较这两个方向哪个路径最小：

*  定义一个同大小的矩阵 distance，用于存放到达当前位置的路径和
 *  第一列和第一行比较特殊，分别只能从上方到达，从左面到达
 *  其余位置要比较从左面，从上面到达，哪个路径和最小，就走选哪个

#### 代码：(Java) ####

public class MinPath {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		
    		int [][] grid = {
        {
        1,3,1},{
        1,5,1},{
        4,2,1}};
    		System.out.println(minPathSum(grid));
    	}
    	public static int minPathSum(int[][] grid) {
        
    		
    		int m = grid.length;
    		int n = grid[0].length;
    		int [][] distance = new int [m][n];
    		
    		distance[0][0] = grid[0][0];
    		
    		for(int i = 1; i < m; i++) {
        
    			distance[i][0] = distance[i-1][0] + grid[i][0];
    		}
    		for(int j = 1; j < n; j++) {
        
    			distance[0][j] = distance[0][j-1] + grid[0][j];
    		}
    		
    		for(int i = 1; i < m; i++) {
        
    			for (int j = 1; j < n; j++) {
        
    				distance[i][j] = Math.min(distance[i-1][j], distance[i][j-1]) + grid[i][j];
    			}
    		}
    		return distance[m-1][n-1];
        }
    }

##### 运行结果： #####

![在这里插入图片描述][246f74b1f0d8417fb37b051759ca8c1b.png]

##### 复杂度分析： #####

时间复杂度 O(M×N) ： 遍历整个 grid矩阵元素。  
空间复杂度 O(M×N) ： 需要和原矩阵相同大小的空间。（\*\*改进：\*\*可以直接在原矩阵修改，就不需要额外空间，此时空间复杂度为O(1)。)

##### 注：仅供学习参考！ #####

题目来源：[力扣。][Link 1]

[6d57f73ce4194643b1946fdad3401423.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/b2e511d4c8864fd282e56aedd69b566d.png
[246f74b1f0d8417fb37b051759ca8c1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d6a48010e8c7447e81e34cc7cf689503.png
[Link 1]: https://leetcode.cn/problems/minimum-path-sum/description/