动态规划-矩阵中的最短路径

一、牛客 NC59 矩阵的最小路径和 给定一个 n * m 的矩阵 a,从左上角开始每次只能向右…

一、牛客 NC59 矩阵的最小路径和

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

数据范围: 1≤n,m≤500,矩阵中任意值都满足 0 ≤ a(i,j) ≤100
要求:时间复杂度 O(nm)O(nm)

例如:当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时,对应的返回值为12,
所选择的最小累加和路径如下图所示:
在这里插入图片描述

或者

二、最短路径

给定一个矩阵,从上到下找到最短路径, 第一行任意位置开始,只能往下走(包含对角线)

矩阵:
{1, 3, 5, 9},
{8, 1, 3, 4},
{5, 0, 6, 1},
{8, 8, 4, 0}
结果输出: 6
解析:
因为路径1->1->0->4 为最短路径,
{1, 3, 5, 9},
{8, 1, 3, 4},
{5, 0, 6, 1},
{8, 8, 4, 0}
变化过程为:
[1, 3, 5, 9]
[9, 2, 6, 9]
[7, 2, 8, 7]
[10, 10, 6, 7]

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/3922.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部