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

相关推荐

  • leetcode78-子集

    原题 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明: 解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3…

    算法 2020年5月24日
    0320
  • leetcode429-N叉树的层序遍历

    原题 给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。 例如,给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明:…

    2020年1月20日
    0140
  • leetcode279-完全平方数

    原题 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出…

    2019年12月11日
    0150
  • leetcode67-二进制求和

    原题 给定两个二进制字符串,返回他们的和(用二进制表示)。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = “11”, b = “1” 输出: “100” …

    算法 2019年11月15日
    0100
  • leetcode86-分隔链表

    原题 给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head…

    算法 2020年4月27日
    0150
  • 剑指offer35-复杂链表的复制

    原题(来源Leetcode) 请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random …

    2020年6月13日
    0110
  • leetcode17-电话号码的字母组合

    原题 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入: "23" 输出: …

    2020年5月3日
    0130
  • leetcode385-迷你语法分析器

    原题 给定一个用字符串表示的整数的嵌套列表,实现一个解析它的语法分析器。 列表中的每个元素只可能是整数或整数嵌套列表 提示: 你可以假定这些字符串都是格式良好的: 字符串非空 字符…

    算法 2020年1月28日
    02260
  • leetcode202-快乐数

    原题 编写一个算法来判断一个数是不是“快乐数”。 一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无…

    算法 2019年12月18日
    0120
  • leetcode7-整数反转

    原题 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 示例2: 输入: -123 输出: -321 示例3: 输…

    算法 2020年2月26日
    0120

发表回复

登录后才能评论