64-最小路径和.md

题目描述

最小路径和

题目简述

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

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

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

分类

中等 动态规划

思路

思路1

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
  grid[0].reduce((total, i, index) => {
    grid[0][index] = total + i
    return total + i
  }, 0)
  for (let i = 1; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (j === 0) {
        grid[i][j] += grid[i - 1][j]
        continue
      }
      grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1])
    }
  }
  return grid.slice(-1)[0].slice(-1)[0]
};

• 问题分析
  • 该题和三角形最小路径和思路类似，都是和上一级去比较，取最小值。
  • 整体思路：
    • 首先计算第一行的，从左往右走的数字总和。接着遍历每行中的列，因为只能向下或向右走，所以从左侧和上方，选出最小值进行相加。最终grid右下角的值就是结果。