leetcode-64. 最小路径和

[francecil]

原题链接

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

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

示例:

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

[francecil]

错误思路：深搜+剪枝

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
  let n = grid.length
  let m = grid[0].length
  let mark = Array(n).fill(Array(m).fill(0))
  let min = Infinity
  function dfs(i,j,sum){
    if(sum>min){
      return
    }
    if(i+1===n&&j+1===m){
      min = Math.min(min,sum)
    }
    if(i+1<n){
      dfs(i+1,j,sum+grid[i+1][j])
    }
    if(j+1<m){
      dfs(i,j+1,sum+grid[i][j+1])
    }
  }
  dfs(0,0,grid[0][0])
  return min
};

最多的情况可能需要深搜每条路径，总共的路径一共有 C(m+n-2,m-1) 种,

组合问题，总共需要走 m+n-2 步，选择其中的 m-1 步向下走 参考题目不同路径

运算次数为 C(m+n-2,m-1)*(m+n-2)，数据量一大就会超时

[francecil]

动态规划

由于每次只能往右或往下走，因此到达网格 grid[i][j] 的最小路径和sum[i][j]为 grid[i][j] + Math.min(sum[i-1][j],sum[i][j-1])

以

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

为例 先计算第一行和第一列的结果，得到

[
  [1,4,5],
  [2, , ],
  [6, , ]
]
计算第二行结果 =>
[
  [1,4,5],
  [2,7,6],
  [6, , ]
]
计算第三行结果 =>
[
  [1,4,5],
  [2,7,6],
  [6,8,7]
]

所以最小路径和为7

代码如下：

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
  let n = grid.length
  let m = grid[0].length
  let sum = Array(n).fill(0).map(v=>Array(m).fill(0))
  sum[0][0] = grid[0][0]
  // 第一列
  for(let i=1;i<n;i++){
    sum[i][0] = grid[i][0]+sum[i-1][0]
  }
  // 第一行
  for(let i=1;i<m;i++){
    sum[0][i] = grid[0][i]+sum[0][i-1]
  }
  for(let i=1;i<n;i++){
    for(let j=1;j<m;j++){
      sum[i][j] = grid[i][j] + Math.min(sum[i-1][j],sum[i][j-1])
    }
  }
  return sum[n-1][m-1]
};

时间复杂度 O(n*m) ，空间复杂度 O(n*m)

如果允许修改原数据的话，可以不用另外的 sum，直接在 gird 上操作， 这样空间复杂度为 O(1)

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

[francecil]

推荐：一维动态规划

我们刚刚用一个二维数组 sum 来统计最小路径和， 但是我们可以发现，在求 sum[i][j] 的时候，只会用到 sum[i-1][j] 和 sum[i][j-1] 其他的什么 sum[i-2][j]，sum[i][j-2]，sum[i-1][j-1] 根本不会用到，所以只需要用一个一维数组就可以做 sum 的效果

代码如下：

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
  let n = grid.length
  let m = grid[0].length
  let sum = Array(m).fill(0)
  sum[0] = grid[0][0]
  // 第一行
  for(let i=1;i<m;i++){
    sum[i] = grid[0][i]+sum[i-1]
  }
  for(let i=1;i<n;i++){
    for(let j=0;j<m;j++){
      if(j===0){
        sum[j] = grid[i][j] + sum[j]
        continue
      }
      sum[j] = grid[i][j] + Math.min(sum[j],sum[j-1])
    }
  }
  return sum[m-1]
};