专栏首页用户画像Leetcode No.64 最小路径和

Leetcode No.64 最小路径和

一、题目描述

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

提示:

m == grid.length n == grid[i].length 1 <= m, n <= 200 0 <= grid[i][j] <= 100

二、解题思路

由于路径的方向只能是向下或向右,因此网格的第一行的每个元素只能从左上角元素开始向右移动到达,网格的第一列的每个元素只能从左上角元素开始向下移动到达,此时的路径是唯一的,因此每个元素对应的最小路径和即为对应的路径上的数字总和。

对于不在第一行和第一列的元素,可以从其上方相邻元素向下移动一步到达,或者从其左方相邻元素向右移动一步到达,元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关,因此可以使用动态规划求解。

创建二维数组 dp,与原始网格的大小相同,dp[i][j] 表示从左上角出发到 (i,j)(i,j) 位置的最小路径和。显然,dp[0][0]=grid[0][0]。对于 dp 中的其余元素,通过以下状态转移方程计算元素值。

当 i>0且 j=0时,dp[i][0]=dp[i−1][0]+grid[i][0]。

当 i=0且 j>0时,dp[0][j]=dp[0][j−1]+grid[0][j]。

当 i>0且 j>0时,dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]。

最后得到 dp[m−1][n−1] 的值即为从网格左上角到网格右下角的最小路径和。

三、代码

class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int[][] dp=new int[m][n];
        dp[0][0]=grid[0][0];
        for(int i=1;i<n;i++){
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        for(int i=1;i<m;i++){
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=Integer.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

四、复杂度分析

时间复杂度:O(mn),其中 m 和 n 分别是网格的行数和列数。需要对整个网格遍历一次,计算 dp 的每个元素的值。

空间复杂度:O(mn),其中 m和 n 分别是网格的行数和列数。创建一个二维数组dp,和网格大小相同。 空间复杂度可以优化,例如每次只存储上一行的 dp 值,则可以将空间复杂度优化到 O(n)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-64-最小路径和

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

    chenjx85
  • 【Leetcode】64. 最小路径和

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

    Leetcode名企之路
  • LeetCode 64. 最小路径和

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

    freesan44
  • LeetCode 64. 最小路径和(DP)

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

    Michael阿明
  • 64. 最小路径和

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

    和蔼的zhxing
  • leetcode 64 | 最小路径和(动态规划)

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

    ACM算法日常
  • ​LeetCode刷题实战64:最小路径和

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 力扣64——最小路径和

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

    健程之道
  • leetcode - 最小路径和

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

    璀错
  • LeetCode 0064. 最小路径和[动态规划详解]

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

    Yano_nankai
  • Leetcode No.112 路径总和

    给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ,判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 t...

    week
  • 【leetcode刷题】20T30-最小路径和

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

    木又AI帮
  • 【leetcode刷题】T158-最小路径和

    https://leetcode-cn.com/problems/minimum-path-sum/

    木又AI帮
  • leetcode-120-三角形最小路径和

    如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

    chenjx85
  • 【Leetcode】120.三角形最小路径和

    如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

    Leetcode名企之路
  • LeetCode 0120. 三角形最小路径和[动态规划详解]

    每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于...

    Yano_nankai
  • LeetCode 0120. 三角形最小路径和

    每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于...

    Yano_nankai
  • LeetCode刷题DAY 36:最小路径和

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

    三猫
  • LeetCode 931. 下降路径最小和(DP)

    下降路径可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券