【刷题日记】64. 最小路径和
本次刷题日记的第 39 篇，力扣题为：64. 最小路径和 ，中等
一、题目描述：
又是一个最小路径和，还记得前面一次我们做的 120. 三角形最小路径和 吗，咱们这一次的思路是不是和上一次一样呢？
是否也可以按照题目要求，找到一些规律，来进行数学运算呢？可以来瞅瞅
二、这道题考察了什么思想？你的思路是什么？
仔细查看一下这个题给出我们的重点信息有哪些：
- 题目中给出了咱们一个表格，每个表格上面会有对应的整数，数字没有规律
- 我们需要从左上角走路到右下角，需要路径和是最小的，题目明确要求，我们只能向右或者向下走，是不能蛇形走位的哦
细心的我们可以发现，整个表格，如果是按照第一行往右走，那么影响因素只有左边这一个，同理，第一列的时候，一直往下走，那么影响因素只有上面一个
就比如说 例子中，3 这个格子，肯定是从 左上角的 1 这个格子走过来的，同理，右上角的这个格子，肯定也是 3 这个格子走过来的
那么除了第一行和第一列，其他的格子是不是也会那么纯粹呢？
例如 5 这个格子，可能是上面的 3 这个格子走下来的，也有可能是左边的 1 这个格子向右走过来的，那么到底是谁走过来的路径是最小的呢？
当然这就依赖于他们之前的路径和是否是最小的了，因为我们就可以这样来推演，如下：
我们创建一个和题目给出的表格一样的二维数组，主要是记录最小路径和
第一行，和第一列，还是刚才说的一样，按照既定的路径和方式进行偏移和计算，当我们计算到其他格子的时候，就需要考虑当前格子，从左边走过来，和从上面走下来，谁路径和最小，谁小，就按照谁的方向来
如上图，这样一来，稍微推演一下，我们的思路就清晰了吧，接下里就开始撸代码吧
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码，这里需要注意这么几个情况
- 单独处理好第一行的数据
- 单独处理好第一列的数据
- 其他剩下的格子，考虑好他的上方和左方的数据，计算最小路径和
func minPathSum(grid [][]int) int { // 校验输入的 grid 是不是表格 if len(grid) == 0 || len(grid[0]) == 0 { return 0 } // 给 dp 分配好空间，与题目给出的 grid 表格保持同样的空间 row,col := len(grid), len(grid[0]) dp := make([][]int, row) for i := 0; i< row ; i++{ dp[i] = make([]int,col) } dp[0][0] = grid[0][0] // 计算，第一行 for j:=1; j<col; j++{ dp[0][j] = dp[0][j-1] +grid[0][j] } // 计算 第一列 for i:=1; i<row; i++{ dp[i][0] = dp[i-1][0] + grid[i][0] } // 计算剩下的格子 for i:=1; i<row; i++{ for j:=1;j<col;j++{ dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + grid[i][j] } } return dp[row-1][col-1] } func min(a,b int)int{ if a<b{ return a } return b }
按照编码逻辑，和咱们的思路是一毛一样的，我们这样做的原因之一是题目给出的规则，只能往右或者往下，所以当前格子，要么是通过往下走移动到的，或者是往右走移动到的
最终，咱们走到表格的右下角，及计算 ok，得到整个链路的最小路径
四、总结：
按照我们这种方式去实现和解决问题，那么时间复杂度对于此题就很明确了吧，相当于咱们就是遍历了给出表格，每个格子咱们都已经遍历到了，所以时间度是 O(nm)，n 可以理解为行，m 可以理解为 列
同理空间复杂度也是 O(nm)，因为咱们也同样开辟了和表格一样的二维数组，产生了空间消耗
原题地址：64. 最小路径和
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
