leetcode64-最小路径和

原题

给定一个包含非负整数的 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)
彭晨涛彭晨涛管理者
上一篇 2020年2月23日 23:28
下一篇 2020年2月24日 20:55

相关推荐

  • leetcode454-四数相加II

    原题 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。 为…

    算法 2019年12月27日
    070
  • leetcode752-打开转盘锁

    原题 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。每个拨轮可以自由…

    2019年12月9日
    0280
  • leetcode169-多数元素

    原题 给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例1:…

    算法 2020年2月5日
    070
  • leetcode104-二叉树的最大深度

    原题 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例:给定二叉树 [3,9,20,null…

    算法 2020年1月11日
    080
  • leetcode145-二叉树的后序遍历

    原题 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2020年1月10日
    070
  • leetcode73-矩阵置零

    原题 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [   [1,1,1],  …

    算法 2020年5月14日
    080
  • leetcode79-单词搜索

    原题 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格…

    算法 2020年4月12日
    0110
  • leetcode278-第一个错误的版本

    原题 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假…

    算法 2020年1月2日
    080
  • leetcode154-寻找旋转排序数组中的最小值II

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。…

    算法 2020年1月7日
    080
  • leetcode167-两数之和II-输入有序数组

    原题 给定一个已按照 升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值index1和index2,其中index1必须小于index2。 说明…

    算法 2019年11月20日
    0160

发表回复

登录后才能评论