问题描述:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
原问题链接:https://leetcode.com/problems/minimum-path-sum/
问题分析
这个问题其实和前面分析unique path的思路基本上一致。我们要求从最左上节点到最右下节点之间的最短距离,而且每次移动只能选择向下或者向右。那么对于初始节点来说,它的最短路径就取决于它的下面那个节点和右边那个节点哪个更小。而要求出它下面的节点和右边的节点的值,则需要进一步看这两个节点的下面和右边的元素。因此,这就构成了一个递推的关系。
再加上前面的一个基础条件,当处在最下面一行和最右边一列的元素,它们的路径是唯一的,所以它们到终点的距离就是它当前的值和到终点元素的和。而对于其他节点的元素,它的最短路径则符合如下的规律:
path[i][j] = path[i][j] + Math.min(path[i + 1][j], path[i][j + 1]);
在具体的实现里,我们可以利用原有的矩阵,而不用去额外声明一个矩阵。这样可以偷点懒。
详细的实现如下:
public class Solution { public int minPathSum(int[][] grid) { int min = 0, m = grid.length, n = grid[0].length; for(int i = n - 2; i >= 0; i--) grid[m - 1][i] += grid[m - 1][i + 1]; for(int i = m - 2; i >= 0; i--) grid[i][n - 1] += grid[i + 1][n - 1]; for(int i = m - 2; i >= 0; i--) { for(int j = n - 2; j >= 0; j--) { grid[i][j] += Math.min(grid[i + 1][j], grid[i][j + 1]); } } return grid[0][0]; } }
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number ...LeetCode ...Sum ...Sum ...Sum ...Minimum Path Sum 73
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。...LeetCode ...LeetCode ...LeetCode ...LeetCode ...LeetCode ...LeetCode ...LeetCode ...LeetCode ...3Sum (271_Medium) LeetCode 17 : 电话号码的
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
leetcode leetcode练习 twosum 问题 ;add two numbers问题;reverse integer问题;最大不重复子字符串长度问题;atoi问题;
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
LeetCode: ://leetcode.com/ 程式语言:C ++ # 标题 解决方案 困难 1个 简单的 2个 中等的 3 中等的 4 难的 5 中等的 6 中等的 7 反整数 7反向整数 简单的 8 字符串到整数(atoi) 8字符串到整数(atoi) ...
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
leetcode 1004 力码 去做 : array , dynamic-programming : link , math : string , sliding-window : array , median : string : string : number , reverse , bit : string : math , bit : string , ...
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码