我要招人

去企业版

首页 > 试题广场 >

矩阵的最小路径和

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

热度指数：95150 时间限制：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]]

输出

备注:

算法知识视频讲解

Python

奋斗的习习张

#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def minPathSum(self , matrix ):
        # write code here
        if not matrix&nbs***bsp;not matrix[0]:
            return 0
        m = len(matrix)
        n = len(matrix[0][0:])
        dp = []
        for i in range(m):
            dp.append(([0]*n))
        dp[0][0] = matrix[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + matrix[i][0]
        for i in range(1, n):
            dp[0][i] = dp[0][i-1] + matrix[0][i]
        for row in range(1, m):
            for col in range(1, n):
                dp[row][col] = min(dp[row-1][col], dp[row][col-1]) + matrix[row][col]
        return dp[-1][-1]

发表于 2021-08-15 22:13:20 回复(0)

Python

Keosu

class Solution:
    def minPathSum(self , matrix ):
        n, m = len(matrix), len(matrix[0])
        for i in range(1, n):
            matrix[i][0] += matrix[i-1][0]
        for j in range(1, m):
            matrix[0][j] += matrix[0][j-1]
        for i in range(1, n):
            for j in range(1, m):
                matrix[i][j] += min(matrix[i-1][j], matrix[i][j-1])
        return matrix[n-1][m-1]

动态规划

发表于 2021-07-12 15:39:30 回复(0)

Python

钱朗

#
#
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
def minPathSum(self , matrix ):
# write code here
m = len(matrix)
n = len(matrix[0])

for i in range(m):
for j in range(n):
if i == j == 0:
continue
elif i == 0:
matrix[i][j] = matrix[i][j-1] + matrix[i][j]
elif j == 0:
matrix[i][j] = matrix[i-1][j] + matrix[i][j]
else:
matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1]) + matrix[i][j]
return matrix[-1][-1]

发表于 2021-06-17 17:06:26 回复(0)

Python

爱睡懒觉的帕丁顿

为什么超时？

class Solution:
def minPathSum(self , matrix ):
# write code here
m = len(matrix)
n = len(matrix[0])
def dfs(x,y):
if x==0 and y==0:
return matrix[0][0]
if x==0:
return dfs(x,y-1)+matrix[x][y]
if y==0:
return dfs(x-1,y)+matrix[x][y]
return matrix[x][y]+min(dfs(x,y-1),dfs(x-1,y))
return dfs(m-1,n-1)

发表于 2021-03-15 10:59:32 回复(0)

Python

LHC0512

Python 记忆化搜索，通过

from functools import lru_cache

class Solution:
    def minPathSum(self, matrix):
        n = len(matrix) - 1
        m = len(matrix[0]) - 1
        self.matrix = matrix
        return self.__gen(n, m)

    @lru_cache(maxsize=4000000)
    def __gen(self, i, j):
        if i > 0 and j > 0:
            return self.matrix[i][j] + min(self.__gen(i - 1, j), self.__gen(i, j - 1))
        elif i > 0:
            return self.matrix[i][j] + self.__gen(i - 1, j)
        elif j > 0:
            return self.matrix[i][j] + self.__gen(i, j - 1)
        else:
            return self.matrix[i][j]

发表于 2021-02-23 17:39:10 回复(0)

Python

sk8_wt

class Solution:
    def minPathSum(self , matrix ):
        rows = len(matrix)
        cols = len(matrix[0])
        dp = [[0]*cols for _ in range(rows)]
        for col in range(cols):
            dp[0][col] = sum(matrix[0][:col+1])
        for row in range(rows):
            sum_ = 0
            for i in range(row+1):
                sum_ += matrix[i][0]
            dp[row][0] = sum_
        for row in range(1,rows):
            for col in range(1,cols):
                dp[row][col] = min(dp[row-1][col],dp[row][col-1])+matrix[row][col]
        return dp[-1][-1]

用python写动态规划，超时，通过62.5%

发表于 2020-08-30 15:51:35 回复(2)

Python

擎天柱领袖

class Solution:
def minPathSum(self , matrix ):
# DP
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if i == j == 0: continue
elif i == 0: matrix[i][j] = matrix[i][j - 1] + matrix[i][j]
elif j == 0: matrix[i][j] = matrix[i - 1][j] + matrix[i][j]
else: matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1]) + matrix[i][j]
return matrix[-1][-1]

case通过率为62.50% 有人能更快的吗

发表于 2020-08-15 20:25:32 回复(3)