算法笔试模拟题精解之“矩阵最小路径和”

简介: 本题可以用动态规划的方法来解决。计算一个格子到右下角的最小路径需要两个数据,一个是右边格子到右下角的最小路径,一个是下边格子到右下角的最小路径,两个数据的较小值加上当前格子的数值即为最小路径。

在线编程产品介绍

阿里云开发者社区在线编程产品,针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等,界面整洁明了,操作简单,为用户营造专心答题的学习环境。
点击链接开始体验:https://developer.aliyun.com/coding

题目描述

难度:简单
知识点:数组、DP

查看题目:34.矩阵最小路径和
给定一个矩阵,大小为m,从左上角开始每次只能向右走或者向下走,最后达到右下角的位置。路径中所有数字累加起来就是路径和,返回所有路径的最小路径和。

示例1
比如输入矩阵为
4 1 5 3
3 2 7 7
6 5 2 8
8 9 4 5

最小路径为
23

解题思路:动态规划

本题可以用动态规划的方法来解决。

计算一个格子到右下角的最小路径需要两个数据,一个是右边格子到右下角的最小路径,一个是下边格子到右下角的最小路径,两个数据的较小值加上当前格子的数值即为最小路径。

dp[i, j] = min(dp[i + 1, j], dp[i, j + 1]) + m[i, j]

由于计算当前格子最小路径需要右边和下边格子的最小路径。因此,需要从底向上进行决策。

本题用动态规划法的难点之一是从底向上进行决策的顺序。

如下图所示,通过观察可以发现,同一对角线上的数字的横纵坐标和是相等的,我们以对角线的方向为顺序,从右下角向左上角计算出每个格子的最小路径。最后可计算得出 dp[0, 0]

3Wjstx.png

是不是有思路了呢,点击链接立刻答题:34.矩阵最小路径和

720-150.png

相关文章
|
9天前
|
存储 SQL 算法
LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
|
5天前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
5天前
|
算法
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
9天前
|
存储 SQL 算法
LeetCode题目112:多种算法实现路径总与改进过程
LeetCode题目112:多种算法实现路径总与改进过程
|
9天前
|
存储 算法 Unix
掌握Unix路径简化:五种有效算法比较【python力扣71题】
掌握Unix路径简化:五种有效算法比较【python力扣71题】
|
9天前
|
存储 算法 数据挖掘
穿越障碍:最小路径和的高效算法比较【python力扣题64】
穿越障碍:最小路径和的高效算法比较【python力扣题64】
|
9天前
|
存储 算法 机器人
路径规划的艺术:不同路径 II 的算法深掘【python力扣63题】
路径规划的艺术:不同路径 II 的算法深掘【python力扣63题】
|
12天前
|
算法 C语言
数据结构与算法——拓扑排序(引例、拓扑排序、伪代码、代码、关键路径问题)
数据结构与算法——拓扑排序(引例、拓扑排序、伪代码、代码、关键路径问题)
11 0
|
13天前
|
存储 算法 Java
【经典算法】LeetCode112. 路径总和(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode112. 路径总和(Java/C/Python3/Go实现含注释说明,Easy)
9 0
|
13天前
|
算法 Java Go
【经典算法】LeetCode 64. 最小路径和(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 64. 最小路径和(Java/C/Python3/Golang实现含注释说明,Easy)
8 1

热门文章

最新文章