1. 代码段小站首页
  2. 算法

leetcode64-最小路径和

彭晨涛 • • 算法 • 阅读 6

原题

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

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

示例:

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

解法

思想

动态规划，用一个数组记录某一个位置最小路径和，从右下角开始，往上一层（斜线）的元素的最小路径和为下面元素的最小路径和与右边元素的最小路径和中的最小值加上当前位置的数字。

当然也可以使用递归+记忆的方法求解，62、63我都是用递归+记忆求解的，这里就不用了。

代码

class Solution {
    public int minPathSum(int[][] grid) {
        int height = grid.length;
        if(height == 0) return 0;
        int width = grid[0].length;
        int[][] pathLength = new int[height][width];
        pathLength[height-1][width-1] = grid[height-1][width-1];
        for(int sum = (height+width-3); sum>=0; sum--){
            for(int i = 0;i<=sum ;i++){
                int j = sum-i;
                if(i>=height||j>=width) continue;
                if(i == height-1) pathLength[i][j] = pathLength[i][j+1] + grid[i][j];
                else if(j == width-1) pathLength[i][j] = pathLength[i+1][j] + grid[i][j];
                else pathLength[i][j] = Math.min(pathLength[i][j+1] ,pathLength[i+1][j])+ grid[i][j];
            }
        }
        return pathLength[0][0];
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode64-%e6%9c%80%e5%b0%8f%e8%b7%af%e5%be%84%e5%92%8c/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年2月23日 23:28
下一篇 2020年2月24日 20:55

相关推荐

发表回复

登录后才能评论