原题
给定一个包含非负整数的 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/
相关推荐
-
leetcode680-验证回文字符串II
原题 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。 示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出: True 解...
-
leetcode66-加一
原题 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以...
-
leetcode682-棒球比赛
原题 你现在是棒球比赛记录员。给定一个字符串列表，每个字符串可以是以下四种类型之一：1. 整数（一轮的得分）：直接表示您在本轮中获得的积分数。2. "+"（一轮的得...
-
程序员面试金典01.07-旋转矩阵
原题（来源Leetcode） 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。 不占用额外内存空间能否做到？ 示例 ...
-
leetcode402-移掉K位数字
原题 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。 注意： num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 ...
-
leetcode202-快乐数
原题 编写一个算法来判断一个数是不是“快乐数”。 一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无...
-
leetcode135-分发糖果
原题 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 你需要按照以下要求，帮助老师给这些孩子分发糖果： 每个孩子至少分配到 1 个...
-
leetcode215-数组中的第K个最大元素
原题 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 示例1: 输入： [3,2,1,5,6,4] 和...
-
使用递归函数逆序一个栈
原题（来源：牛客网） 一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现了栈中元素的逆序，请设计...
-
剑指offer44-数字序列中某一位的数字
原题（来源Leetcode） 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位...