题目
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。**
示例:
1 | 输入: |
解释: 因为路径 1→3→1→1→1 的总和最小。
解法:
这道题是一道动态规划的入门题,虽然说用递归是其中一种解,但远不及动态规划灵活。所以我选择不写出递归的解法。
动态规划解题思路
根据说明要求每次只能向下或者向右
那么对于矩阵的任一位置,到该位置的上一步,
必然是它的左边或者上面(第一行、第一列是特例)
那么我们可以设一个等大的矩阵为sum,原矩阵为grid。
从
grid[0][0]
开始,将sum[0][0]
初始化为grid[0][0]
按图中所给例子 即为 1
sum的作用是储存路径和
第一行是特例,sum[1][0]
的值便为 1+3 = 4 ,sum[2][0]
就是4+1 =5
第一列同上sum[0][1]
是 1+ 1 =2 ,sum[0][2]
是 2 + 4 =6处理完特殊情形我们就可以从
grid[1][1]
开始了根据所给例子
grid[1][1]=5
在 sum矩阵中的上方及左方是 4 和 2 在这两个数中取最小值与grid[1][1]
相加,也就是 5 + 2 = 7 ,将结果储存至sum[1][1]
同上
grid[2][1]= 1
需要在 7 和 5 中去取最小值,sum[2][1]
=5+1=6按照这个思路,在
sum[2][2]
就能得到我们想要的结果 7 了
代码实现
1 | int Solution::minPathSum(vector<vector<int>> &grid) { |
当然这段代码是能完成我所述思路的,但是还有更优秀的写法,还能缩短代码运行时间。
- 本文作者: TangZ
- 本文链接: http://wstzj.github.io/2020/07/19/学习笔记-Leetcode最小路径和/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!