JAVA算法练习（13）：最小路径和

​​​​​

​ 最小路径和

活动地址：CSDN21天学习挑战赛

一、题目

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

示例 1：

图 1.1

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

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
通过次数402,143提交次数580,008

代码填充模板：
class Solution {
public int minPathSum(int[ ][ ] grid) { }
}

二、解题

• 在这个题目上，最简单暴力的方法无疑是深度优先遍历，但是深度优先遍历需要用到的是递归，在该题已经给出的代码模板上我们可以看出，该题是不支持我们进行递归操作的，因为该题进行递归的算法最起码需要一个计算数值的辅助变量；
• 因为不能使用递归，那么深度优先遍历和递推都不能够在这个题目上应用，能够解决这个方法的其他方法主要有转换成矩阵问题（ 将其看作一个图形结构，将其转换成邻接矩阵进行寻找最短路径 ）或者枚举法，而在枚举法当中如果将其转换成背包问题，无疑是更优的，故在解此题的过程中选用了该方法；

2.1

• 根据题目提示我们建立两个变量，一个存储行数，一个存储列数；
• 建立一个计算路径的辅助数组，行列数与传入的数组相同；

图 2.1

2.2

• 将辅助数组赋初值，因为需要计算的是最小路径，故这边将整个数组进行赋值为整型最大的数，方便后续进行计算；
• 将第一个位置上的元素赋值为所传数组的第一个位置上的值；（因为要使用的是背包方法解决问题，而在初始的情况下只有第一个位置的元素存在）

图 2.2

2.3

• 建立两个循环进行对整个数组进行枚举；
• 进行双重背包解题，如果不是第一个元素，则将横 (纵) 坐标减一的辅助数组数组与所传入数组相加，值得注意的是更变纵坐标时前面可能会做过一次横坐标减一的情况，故要对两个结果取一个较小值；
• 最后返回辅助数组最末尾的一个元素就是最小路径；

图 2.3

三、代码分享及力扣评分

3.1 力扣评分

• 内存消耗有起伏，在 43.8 - 44 之间；

图 3.1

3.2 代码分享

class Solution {
    public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] dp = new int[n][m];
        for( int i = 0; i< n; i++)
            for( int j = 0; j < m; j++){
                dp[i][j] = Integer.MAX_VALUE;
            }
        dp[0][0] = grid[0][0];


        for( int i = 0; i< n; i++)
            for( int j = 0; j < m; j++){
                if( i > 0 )
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                if( j > 0 )
                    dp[i][j] = Math.min( dp[i][j] , dp[i][j-1] + grid[i][j] );
            }
        return dp[n-1][m-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22