最小路径和-力扣64-java 动态规划-Toy模板网

这篇具有很好参考价值的文章主要介绍了最小路径和-力扣64-java 动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目描述

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

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

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]

输出：7

解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]

输出：12

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/minimum-path-sum

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、运行结果

三、解题思路

采用动态规划的思想，定义一个和原矩阵相同大小的动态矩阵dp，从最左上角到达矩阵中的任意一个位置：第一行的每个位置只能从左边一个位置到达，第一列的每个位置只能上一个位置到达，所以先初始化dp矩阵的第一行和第一列。

对于其他每个位置，可以从上一个位置向下走一步到达，也可以从左一个位置向右走一步到达，取决于从哪个方向走长度较短，所以状态转移方程为：

dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

按照这个方程填满dp中的每个格子，最终得到dp[row-1][col-1](最右下角的位置)的值就是最短路径的长度。文章来源地址https://www.toymoban.com/news/detail-408657.html

四、AC代码

class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = grid[0][0];   //初始化
        for(int i=1; i<row; i++)
            dp[i][0] = grid[i][0] + dp[i-1][0]; //初始化第一列（累加）
        for(int j=1; j<col; j++)
            dp[0][j] = grid[0][j] + dp[0][j-1];  //初始化第一行（累加）
        for(int i=1; i<row; i++){
            for(int j=1; j<col; j++){
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; //状态转移方程
            }
        }
        return dp[row-1][col-1];  //返回最右下角的元素
    }
}

到了这里，关于最小路径和-力扣64-java 动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！