LeetCode-64-最小路径和
# LeetCode-64-最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
示例：
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
# 解题思路
方法1、动态规划：
特例判断：当行或者列为空，行列其中一个为0的时候，数组没有意义，直接返回0
由于只能往下或者往右走，所以第一行和第一列的值始终是由单个方向移动得到
这一部分的值可以先通过循环累加得到
剩下的位置，以i=1，j=1的位置，数字5为例，数字5位置的最小值可以由，Min(上方位置的值+5，左方位置的值+5)计算得到
所以当前的状态可以定义为：从左方和右方计算得到的当前位置的路径最小值
不难看出，数值可以在原本的数组中原地改变且不影响结果。
状态转移方程为：
grid[i][j] = Math.min(grid[i-1][j]+grid[i][j],grid[i][j-1]+grid[i][j]);
由于当前位置始终存储到达该位置的路径最小值，则最后到达右下角时，就是该矩阵中到达右下角总和最小的路径和
横向按顺序遍历的方法类似，这里不再重复介绍，详见Python代码
# Java代码
class Solution {
public int minPathSum(int[][] grid) {
int rowlen = grid.length;
int collen = grid[0].length;
if(grid==null||rowlen==0||grid[0]==null||collen==0){
return 0;
}
for(int i=1;i<collen;i++){
grid[0][i] += grid[0][i-1];
}
for(int j=1;j<rowlen;j++){
grid[j][0] += grid[j-1][0];
}
for(int i=1;i<rowlen;i++){
for(int j=1;j<collen;j++){
grid[i][j] = Math.min(grid[i-1][j]+grid[i][j],grid[i][j-1]+grid[i][j]);
}
}
return grid[rowlen-1][collen-1];
}
}
# Python代码
class Solution:
def minPathSum(self, grid: [[int]]) -> int:
for i in range(len(grid)):
for j in range(len(grid[0])):
if i == j == 0: continue
elif i == 0: grid[i][j] = grid[i][j - 1] + grid[i][j]
elif j == 0: grid[i][j] = grid[i - 1][j] + grid[i][j]
else: grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
return grid[-1][-1]本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-07-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录