首页 > 试题广场 >

矩阵的最小路径和

[编程题]矩阵的最小路径和
  • 热度指数：95150 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

数据范围: ，矩阵中任意值都满足
要求：时间复杂度

例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12，
所选择的最小累加和路径如下图所示：

示例1

输入

[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]

输出

12
示例2

输入

[[1,2,3],[1,2,3]]

输出

7

备注:
1 \leq a_{i,j} \leq 100
算法知识视频讲解
开通博客
头像 牛客786963925号
发表于 2021-07-07 15:58:10
精华题解 解法一：回溯法（暴力解法） 回溯法遍历所有可走到的路线，并计算每条路线的结果，将最小的结果返回。回溯方法通常需要两个步骤：1. 更新变量，递归到下一步；2.递归返回时，撤销更新对于此题，在每一次递归过程中，需要将当前位置元素的路径和(代码中curSum变量)加入到结果中，并作为参数传入下一次递归；在 展开全文
去ta的博客 赞 (29) 回复(4) 收起
头像 牛客题解官
发表于 2022-04-22 12:43:03
精华题解 题目主要信息: 给定一个矩阵，从矩阵左上角到右下角，每次只能向下或者向右 从左上角到右下角路径上经过的所有数字之和为路径和，求该路径和的最小值 矩阵不为空，每个元素值都为非负数 举一反三： 学习完本题的思路你可以解决如下题目： BM67.不同路径的数目(一) 方法：动态规划（推荐使用） 知识点： 展开全文
去ta的博客 赞 (11) 回复(4) 收起
头像 数据结构和算法
发表于 2021-04-02 11:02:59
1，动态规划求解 这题求的是从左上角到右下角，路径上的数字和最小，并且每次只能向下或向右移动。所以上面很容易想到动态规划求解。我们可以使用一个二维数组dp，dp[i][j]表示的是从左上角到坐标(i，j)的最小路径和。那么走到坐标(i，j)的位置只有这两种可能，要么从上面(i-1，j)走下来，要么从 展开全文
去ta的博客 赞 (19) 回复(4) 收起
头像 牛客187993744号
发表于 2020-09-08 10:40:36
题目描述给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。 题解第一行 只能从左往右第一个元素 的值为 原数组的第一个元素 dp[0][0] = a[0][0]dp[0][j] = a 展开全文
去ta的博客 赞 (18) 回复(0) 收起
头像 LifelongCode
发表于 2020-12-29 21:03:15
解法1：暴力递归： 因为是从左上角到右下角，只能向右或者向下， 可以使用递归， 把问题简化为：当前位置(i, j)和右边位置(i + 1, j)和下面位置(i, j + 1)之间的问题 base case： 当i == row - 1 && j == col - 1时，位于矩阵 展开全文
去ta的博客 赞 (10) 回复(2) 收起
头像 王清楚
发表于 2020-12-16 12:05:02
设表示走到位置需要的最小路径和那首先，第一行和第一列是确定的，其余位置但是可以发现，其实不用新开辟一个dp数组，直接在原数组上更新也可以c++ class Solution { public: int minPathSum(vector<vector<int> >& 展开全文
去ta的博客 赞 (5) 回复(2) 收起
头像 小洋芋热爱NLP
发表于 2021-01-10 21:42:12
- 1、题目描述： - 2、题目链接：https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb?tpId=196&&tqId=37157&rp=1&ru=/activity/oj&q 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 热血的垂耳兔在求职
发表于 2021-09-27 19:54:44
还是矩阵动态规划，仍然是分析点 （i,j），只能通过（i-1,j)下移或（i,j-1)右移到达。那么令dp（i,j)为到达（ij）最短的路径，有如下关系：dp(i,j) = min( dp(i, j-1), dp(i-1, j) ) + P(i, j)其中P(i, j)为点(i,j)的值。这核心的关 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 牛客82035003号
发表于 2022-09-14 22:05:17
1、为了节省空间，就不专门建二维数组存储路径和，而直接在原数组中记录，将每个位置的权值改为到该位置的最短路径。 2、先处理首行，每个位置只可能从左边来，route[0][i]=route[0][i]+route[0][i-1]，即从第二个位置开始均要加上前面位置的路径。 3、然后处理首列 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 勤奋的猫
发表于 2022-05-15 16:04:10
import java.util.*; public class Solution {     /**      *      展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 下一次什么时候可以修改昵称
发表于 2020-10-29 14:32:08
算法 1.动态规划：dp[i][j]表示(0,0)到(i,j)位置的最小路径和 2.初始状态：dp[i][0] = dp[i-1][0] + matrix[i][0]；dp[0][i] = dp[0][i-1] + matrix[0][i] 3.过渡公式：dp[i][j] = Math.min(dp 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 加油做题
发表于 2022-06-19 21:29:20
直接在原矩阵上操作即可 int minPathSum(int** matrix, int matrixRowLen, int* matrixColLen ) { for(int i=0;i<matrixRowLen;i++){ for(int j=0;j<*ma 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

动态规划 数组
难度：
208条回答 10768浏览

热门推荐

通过挑战的用户

查看代码

相关试题

矩阵的最小路径和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号