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

在线编程产品介绍

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

点击链接开始体验：

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]。

是不是有思路了呢，点击链接立刻答题：

34.矩阵最小路径和