64.最小路径和

64.最小路径和

Category	Difficulty	Likes	Dislikes
algorithms	Medium (69.47%)	1436	-

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

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

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

---

Discussion | Solution

思路

这个实现的主要思路是使用动态规划，创建一个新的二维数组 grid 来记录每个网格的最小路径和。同时使用变量 top 和 left 来记录当前行和上一行中对应列的最小路径和。对于每个网格，使用其上面和左边的最小路径和进行比较，并将最小值加上当前网格的值，存储到 grid 数组中。
具体来说，代码的步骤如下：

1. 创建一个数组 top 来存储上一行中每列的最小路径和，初始化为一个空数组。同时创建一个变量 left 来存储当前行中前一列的最小路径和，初始化为 0。
2. 遍历整个网格，对于每个网格：
   • 如果该网格是第一行，则将该网格的值加上变量 left 的值，并存储到 grid 数组中。
   • 如果该网格是第一列，则将该网格的值加上数组 top 对应列的值，并存储到 grid 数组中。
   • 如果该网格不是第一行和第一列，则将该网格的值加上数组 top 对应列和变量 left 的最小值，并存储到 grid 数组中。
   • 更新变量 left 为当前网格的值，将当前网格的值存储到数组 top 对应列中。
3. 返回 grid 数组中右下角网格的值，即为最小路径和。

这段代码的时间复杂度为 O(mn)，其中 m 和 n 分别为网格的行数和列数。

解答

/*
 * @lc app=leetcode.cn id=64 lang=javascript
 *
 * [64] 最小路径和
 */

// @lc code=start
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  const top = [];
  let left = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      const topNum = top[j] ? top[j] : 0;
      if (i === 0) {
        grid[i][j] += left;
      } else if (j === 0) {
        grid[i][j] += topNum;
      } else {
        grid[i][j] += Math.min(left, topNum);
      }
      left = grid[i][j];
      top[j] = grid[i][j];
    }
  }
  return grid[grid.length - 1][grid[grid.length - 1].length - 1];
};
// @lc code=end