在线编程产品介绍
阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。
点击链接开始体验：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.矩阵最小路径和
