首页 > 试题广场 >

矩阵的最小路径和

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

输入描述:
第一行输入两个整数 n 和 m，表示矩阵的大小。

接下来 n 行每行 m 个整数表示矩阵。


输出描述:
输出一个整数表示答案。
示例1

输入

4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0

输出

12

备注:

算法知识视频讲解
添加回答
Python
小小201803131558955头像 小小201803131558955
第一步：用input()或者sys.stdin.readline()读数（ps：容易遗忘）
第二步：将读的数据转化矩阵并修改格式为整数
row,clo = map(int, sys.stdin.readline().strip().split())
mat = [[int(v) for v in sys.stdin.readline().strip().split()] for i in range(row)]
第三步：第一种情况：列和行或者矩阵为空的情况，输出为0
第四步：第二种情况：输入是一行数据，结果就有一个，就是sum(mat[0])
第五步：第三种情况：输入是一列数据，结果就有一个，所有元素相加，小心python取法
for j in range(1,row):
     mat[j][0]= mat[j][0]+mat[j-1][0]
结果是mat[row-1][0]
第六步：第四种情况：输入二维数组，新建矩阵newMat，第一行的元素只能向右走，那么新矩阵的第一行元素值就是newMat[0[[j] = mat[0][j]+mat[0][j-1],第一列元素只能向下走，那么新矩阵的第一列元素就是newMat[i][0]= mat[i][0]+mat[i-1][0],再从下标为1，1开始，newMat[1][1]的值是newMat[1][1]=mat[1][1]+min（newMat[0][1]，newMat[1][0])，依次类推：newMat[i][j] = mat[i][j]+min（newMat[i-1][j]，newMat[i][j-1])

发表于 2020-06-07 18:08:29 回复(0)
Python
圣诞节的安徒生头像 圣诞节的安徒生 
def shortestRoadSum(arr, n, m):
    #生成n行m列的0矩阵dp
    dp = [[0 for i in range(m)] for j in range(n)]
    dp[0][0] = arr[0][0]
    for i in range(1, n):
        #第一列只能由上向下走
        dp[i][0] = dp[i-1][0] + arr[i][0]
    for j in range(1, m):
        #第一行只能由左向右走
        dp[0][j] = dp[0][j-1] + arr[0][j]
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + arr[i][j]
    return dp[n-1][m-1]

n, m = map(int, input().split())
#输入二维矩阵
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))
print(shortestRoadSum(arr, n, m))
python在输入二维矩阵时不用先生成全是0的空矩阵了，否则会超时
求最短路径和还可以优化，待完善！
空间复杂度为O(1)的来了： 
def shortestPathSum(arr, n, m):
    #直接修改arr
    for i in range(1, n):
        #第一列只能由上向下走
        arr[i][0] = arr[i-1][0] + arr[i][0]
    for j in range(1, m):
        #第一行只能由左向右走
        arr[0][j] = arr[0][j-1] + arr[0][j]
    for i in range(1, n):
        for j in range(1, m):
            arr[i][j] = min(arr[i-1][j], arr[i][j-1]) + arr[i][j]
    return arr[n-1][m-1]
n, m = map(int, input().split())
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))
print(shortestPathSum(arr, n, m))
牛客的是否ac可能和网速和服务器有关，不稳定，同时python与其他语言比起来，运行时间确实算长的，毕竟是解释型语言，感觉每次都走在超时的边缘

运行最快的来了： 
def shortestRoadSum(arr, n, m):
    # 每次只保留一行结果
    dp = arr[0]
    # 更新第一行的结果
    for j in range(1, m):
        # 第一行只能由左向右走
        dp[j] += dp[j - 1]
    for i in range(1, n):
        dp[0] += arr[i][0] #每一行开始遍历时更新第一个元素
        for j in range(1, m):
            dp[j] = min(dp[j-1],dp[j]) + arr[i][j]
    return dp[-1]

n, m = map(int, input().split())
# 输入二维矩阵
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))
print(shortestRoadSum(arr, n, m))
使用一维矩阵来保存每一行的最优结果，想明白的感觉真好

编辑于 2019-08-14 11:11:36 回复(1)
提交观点

问题信息

动态规划 高级算法
上传者：小小
难度：
2条回答 12310浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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