原题
给定一个包含非负整数的 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/
