04—最小路径和 【LeetCode64】

题目

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

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

示例一：

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

示例二：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= gridi <= 200

解题

解法一

思路

由于题中指出“每次只能向下或者向右移动一步。”，因此本题还是相对比较简单的。

首先定义一个数组dp[][]长度大小和题给数组相同，dp[i][j]数组中存储的是到达每个索引处的最短路径。通过循环可以将dp[][]填满。由于每次只能向下或者向右移动一步，因此第一列和第一行的可以优先快速被填充完，然后接下来再继续填充中间的数组即可。

解决

class Solution {
    public int minPathSum(int[][] grid) {
        //首先初始化定义一个和题给数组大小一样的数组，dp用来记录最短路径
        int[][] dp = new int[grid.length][grid[0].length];
        //第一个位置的路径是固定
        dp[0][0] = grid[0][0];
        //将第一列进行填充
        for(int i=1;i<grid.length;i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        //将第一排填充
        for(int i=1;i<grid[0].length;i++){
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        //开始填充中间部分，将上和左进行对比，选择最小的路径作为当前的路径
        for(int i=1;i<grid.length;i++){
            for(int j=1;j<grid[0].length;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}

结果

> 2023/07/14 14:36:58    
解答成功:
    执行耗时:2 ms,击败了92.29% 的Java用户
    内存消耗:42.7 MB,击败了88.21% 的Java用户