最小路径和(Java)

举报
玉面大蛟龙 发表于 2023/07/20 21:22:06 2023/07/20
【摘要】 一、题目描述 给定一个包含非负整数的 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 == g...

一、题目描述
 

给定一个包含非负整数的 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] <= 100
 

二、思路讲解

        2.1、暴力搜索(超时)

        看到二维数组的题,我会先考虑能不能暴力搜索,思路是找自己右方和下方更小的那条路。

class Solution {
 
    int [][]grid;
 
    public int minPathSum(int[][] grid) {
        this.grid = grid;
        return dfs(0, 0);
    }
 
    int dfs(int i, int j) {
        if(i==grid.length-1 && j==grid[0].length-1) {
            return grid[i][j];
        }
        if(i==grid.length-1) {
            return dfs(i, j+1) + grid[i][j];
        }
        if(j==grid[0].length-1) {
            return dfs(i+1, j) + grid[i][j];
        }
        return Math.min(dfs(i, j+1), dfs(i+1, j)) + grid[i][j];
    }
}

 

        2.2、动态规划(二维dp数组)

        既然dfs行不通,那我们就试试dp。不难看出,走到每个位置的路径和取决于他上方的格子的路径和 or 左方格子的路径和,因此我们用dp[ i ][ j ]来表示走到(i,j)位置的最小路径和,易得递推公式:dp[i][j] = min{ dp[i-1][j] , dp[i][j-1] } + grid[i][j]

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int [][]dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for(int i=1; i<m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int i=1; i<n; i++) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for(int i=1; i<m; i++) {
            for(int j=1; j<n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

 

        2.3、动态规划(一维dp数组)

        接下来我们就来思考如何优化空间。画图可得,我们在动态规划时,是按照一行一行逐步dp的,下一行的值只由上一行和当前行决定,所以我们可以只保留上一行的数据,这样只需要用到一维数组。 

        这样的优化思路可参考:告别动态规划,连刷 40 道题,我总结了这些套路,看不懂你打我(万字长文) - 知乎

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int []dp = new int[n];
        dp[0] = grid[0][0];
        for(int i=1; i<n; i++) {
            dp[i] = dp[i-1] + grid[0][i];
        }
        for(int i=1; i<m; i++) {
            dp[0] = dp[0] + grid[i][0];
            for(int j=1; j<n; j++) {
                dp[j] = Math.min(dp[j-1], dp[j]) + grid[i][j];
            }
        }
        return dp[n-1];
    }
}

        2.4、动态规划(不使用额外空间)

        接2.2的思路,我们其实可以在原数组上直接修改,这样就不使用额外空间了。不过面试的时候有可能会要求不能更改原数组,这种情况下2.3是最优的思路。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。