力扣题解64-最小路径和

• 题目描述
• 分析
  • 状态转移方程
  • 备忘录
  • 边界处理
• 题解
  • 写法一
  • 写法二
• BMW WARNING

题目描述

leetcode 64. 最小路径和

给定一个包含非负整数的 $m \times n$ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

分析

状态转移方程

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

备忘录

设定upRets为一个一维数组，这里需要注意，作为备忘录功能，取j值是刚好是其上侧来的值，取其j-1的值为左侧来的值；
对于这句话的理解，upRets缓存可上一轮最优路径的值，但是新一轮中，每一次循环，都将用upRets[j] = ret进行更新，使得其保留左侧的值

边界处理

本题的关键是第一行和第一列的边界处理，容易出错

• 第一行第一列置初始置为0
• 若第一行，则不能由上侧来，只能由左侧
• 若第一列，则不能由左侧来，只能由上侧

题解

写法一

参照分析，如下

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
  let ret = 0
  let upRets = [0] // 第一行第一列特殊边界处理

  for (var i = 0; i < grid.length; i++) {
    for (var j = 0; j < grid[i].length; j++) {
      let top = isNaN(upRets[j]) ? Number.MAX_SAFE_INTEGER : upRets[j] // 是否为第一行，如果是，则不能由上侧来，只能由左侧
      let left = isNaN(upRets[j - 1]) ? top : upRets[j - 1] // 是否为第一列，如果是，则不能由左侧来，只能由上侧
      ret = Math.min(top, left) + grid[i][j]
      upRets[j] = ret
    }
  }
  return ret

};

写法二

代码稍作整合，如下

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
  let rets = []
  let ret = 0
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      ret = (rets[j] < rets[j - 1] ? rets[j] : isNaN(rets[j - 1]) ? (rets[j] || 0) : rets[j - 1]) + grid[i][j] // 边界处理包含其中，不如发一明显好理解
      rets[j] = ret
    }
  }

  return ret
};

BMW WARNING

• Bulletin

本文首发于 skyline.show 欢迎访问。
文章实时更新，如果有什么错误或不严谨之处望请指出，十分感谢。
如果你觉得有用，欢迎到Github仓库点亮⭐️

I am a bucolic migant worker but I never walk backwards.

• Material

参考资料如下列出，部分引用可能遗漏或不可考，侵删。

• Warrant

本文作者： Skyline(lty)

文章链接：http://www.skyline.show/力扣题解64-最小路径和.html

授权声明： 本博客所有文章除特别声明外， 均采用 CC BY - NC - SA 3.0 协议。 转载请注明出处！