0064._Minimum_Path_Sum

发表于 分类于 ， ，

62. Unique Paths 不同路径

难度: Medium

刷题内容

原题连接

内容描述

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

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

示例:

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

解题方案

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

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

这样一次循环即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @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
};