首页 > 试题广场 >

矩阵动态规划

[编程题]矩阵动态规划
  • 热度指数：617 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
     现有一个地图，由横线与竖线组成（参考围棋棋盘），且两点之间有行走距离起点为左上角，终点为右下角在地图上，每次行走只能沿线移动到临近的点，并累加路径计算一个人从地图的起点走到终点的最小路径为多少。

输入描述:
m*n地图表示如下:

3
3
1 3 4
2 1 2
4 3 1

其中m=3，n=3 表示3*3的矩阵

行走路径为：下>右>右>下


输出描述:
路径总长：1+2+1+2+1=7
示例1

输入

1
2
1 2

输出

3
示例2

输入

2
3
9 8 6
2 3 7

输出

21

备注:
地图参数为：
1
2

1 2

m=1，n=2，表示1*2的矩阵，最短距离是左>右
算法知识视频讲解
添加回答
Python
maoxiaomao头像 maoxiaomao
动态规划状态更新：dp[i][j]=min(dp(上一个格子)+当前cost，dp(左边格子)+当前cost) 
m=int(input().strip())
n=int(input().strip())
M=[]
for i in range(m):
    M.append(list(map(int,input().strip().split())))
dp=[[0]*(n) for _ in range(m)]
for i in range(m):
    for j in range(n):
        if i-1>=0:
            up=dp[i-1][j]+M[i][j]
        else:up=dp[i][j-1]+M[i][j]
        if j-1>=0:
            left=dp[i][j-1]+M[i][j]
        else:left=dp[i-1][j]+M[i][j]
        dp[i][j]=min(up,left);
print(dp[-1][-1])


编辑于 2021-05-31 15:28:25 回复(0)
Python
Jason_kkk头像 Jason_kkk 
m = int(raw_input())
n = int(raw_input())
matrix = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
    line = raw_input().split(' ')
    for j in range(n):
        matrix[i][j] = int(line[j])

dp = [[0 for _ in range(n)] for _ in range(m)]  # dp[i][j] means the min val when arrive at matrix[i][j]
dp[0][0] = matrix[0][0]
for i in range(1, m):
    dp[i][0] = dp[i - 1][0] + matrix[i][0]
for j in range(1, n):
    dp[0][j] = dp[0][j - 1] + matrix[0][j]
for i in range(1, m):
    for j in range(1, n):
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]
print dp[m - 1][n - 1]


发表于 2021-05-16 23:49:59 回复(0)
提交观点

问题信息

C++工程师 golang工程师 算法工程师 PHP工程师 2020 58集团 Java工程师
上传者：小小
难度：
2条回答 3976浏览

热门推荐

通过挑战的用户

相关试题

矩阵动态规划

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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