0064._Minimum_Path_Sum.md

62. Unique Paths 不同路径

难度: Medium

刷题内容

原题连接

• https://leetcode-cn.com/problems/minimum-path-sum/

内容描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

 输入:
 [
   [1,3,1],
   [1,5,1],
   [4,2,1]
 ]
 输出: 7
 解释: 因为路径 1→3→1→1→1 的总和最小。

解题方案

- 时间复杂度: O(MN)- 空间复杂度: O(1)*****

每个坐标的最小期望 = Min(上侧的最小期望， 左侧的最小期望) + 当前坐标值。

这样一次循环即可。

代码：

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
  const height = grid.length
  const width = grid[0].length
  if (width === 1) {
    return grid.reduce((cur, pre) => (cur + pre[0]), 0)
  }
  if (height === 1) {
    return grid[0].reduce((cur, pre) => (cur + pre), 0)
  }
  let min = 0
  for (let i = 0; i < width; i++) {
    for (let j = 0; j < height; j++) {
      if (j === 0 && i === 0) {
        grid[j][i] = grid[j][i]
      } else if (j === 0) {
        grid[j][i] = grid[j][i] + grid[j][i - 1]
      } else if (i === 0) {
        grid[j][i] = grid[j][i] + grid[j - 1][i]
      } else {
        grid[j][i] = grid[j][i] + Math.min(grid[j][i - 1], grid[j - 1][i])
      }
      min = grid[j][i]
    }
  }
  return min
};