我要招人

去企业版

首页 > 试题广场 >

矩阵的最小路径和

[编程题]矩阵的最小路径和

热度指数：86073 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

数据范围: $1 \le n,m\le 500$ ，矩阵中任意值都满足 $0 \le a_{i,j} \le 100$

要求：时间复杂度 $O(nm)$

例如：当输入[[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]]

输出

示例2

输入

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

输出

备注:

算法知识视频讲解

牛客786963925号

发表于 2021-07-07 15:58:10

精华题解解法一：回溯法（暴力解法）回溯法遍历所有可走到的路线，并计算每条路线的结果，将最小的结果返回。回溯方法通常需要两个步骤：1. 更新变量，递归到下一步；2.递归返回时，撤销更新对于此题，在每一次递归过程中，需要将当前位置元素的路径和(代码中curSum变量)加入到结果中，并作为参数传入下一次递归；在展开全文

牛客题解官

发表于 2022-04-22 12:43:03

精华题解题目主要信息: 给定一个矩阵，从矩阵左上角到右下角，每次只能向下或者向右从左上角到右下角路径上经过的所有数字之和为路径和，求该路径和的最小值矩阵不为空，每个元素值都为非负数举一反三：学习完本题的思路你可以解决如下题目： BM67.不同路径的数目(一) 方法：动态规划（推荐使用）知识点：展开全文

数据结构和算法

发表于 2021-04-02 11:02:59

1，动态规划求解这题求的是从左上角到右下角，路径上的数字和最小，并且每次只能向下或向右移动。所以上面很容易想到动态规划求解。我们可以使用一个二维数组dp，dp[i][j]表示的是从左上角到坐标(i，j)的最小路径和。那么走到坐标(i，j)的位置只有这两种可能，要么从上面(i-1，j)走下来，要么从展开全文

牛客187993744号

发表于 2020-09-08 10:40:36

题目描述给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。题解第一行只能从左往右第一个元素的值为原数组的第一个元素 dp[0][0] = a[0][0]dp[0][j] = a 展开全文

LifelongCode

发表于 2020-12-29 21:03:15

解法1：暴力递归：因为是从左上角到右下角，只能向右或者向下，可以使用递归，把问题简化为：当前位置(i, j)和右边位置(i + 1, j)和下面位置(i, j + 1)之间的问题 base case：当i == row - 1 && j == col - 1时，位于矩阵展开全文

王清楚

发表于 2020-12-16 12:05:02

设表示走到位置需要的最小路径和那首先，第一行和第一列是确定的，其余位置但是可以发现，其实不用新开辟一个dp数组，直接在原数组上更新也可以c++ class Solution { public: int minPathSum(vector<vector<int> >& 展开全文

小洋芋热爱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 展开全文

热血的垂耳兔在求职

发表于 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)的值。这核心的关展开全文

勤奋的猫

发表于 2022-05-15 16:04:10

import java.util.*; public class Solution { /** * 展开全文

下一次什么时候可以修改昵称

发表于 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 展开全文