64. 最小路径和：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。-Toy模板网

这篇具有很好参考价值的文章主要介绍了64. 最小路径和：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

64. 最小路径和：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

思路

使用动态规划的方法解决：文章来源地址https://www.toymoban.com/news/detail-474768.html

路径的方向只能是向下或向右
网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和
不在第一行和第一列的元素：以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值
图例：此时是第一行和第一列；原始数组对应的dp数组是对应路径上的数字综合
如下，不在第一行和第一列；此时对应dp数组的元素为其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值

6. 由以上分析可知，其方程如下：

代码

class Solution {
    public int minPathSum(int[][] grid) {
        //如果grid数组为空
        if(grid == null || grid.length == 0 || grid[0].length == 0){
            return 0;
        }
        //获取行列
        int rows = grid.length,clumns = grid[0].length;
        //创建目标数组
        int[][] dp = new int[rows][clumns];
        //为第一行第一列元素赋值
        dp[0][0] = grid[0][0];
        //在第一行时
        for(int i=1;i<rows;i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        //在第一列时
        for(int j=1;j<clumns;j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        //非第一行第一列
        //循环行
        for(int i=1;i<rows;i++){
            //循环列
            for(int j=1;j<clumns;j++){
                //获取最小的为目标数组当前元素的值
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[rows-1][clumns-1];

    }
}

到了这里，关于64. 最小路径和：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！