最小路径和

二题目

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

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {

};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三解题思路

直接报错：

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory

致命错误：无效的标记压缩接近堆限制分配失败-JavaScript堆内存不足

就是当它要执行的数组为：

console.log(minPathSum(
  [
    [7,1,3,5,8,9,9,2,1,9,0,8,3,1,6,6,9,5],
    [9,5,9,4,0,4,8,8,9,5,7,3,6,6,6,9,1,6],
    [8,2,9,1,3,1,9,7,2,5,3,1,2,4,8,2,8,8],
    [6,7,9,8,4,8,3,0,4,0,9,6,6,0,0,5,1,4],
    [7,1,3,1,8,8,3,1,2,1,5,0,2,1,9,1,1,4],
    [9,5,4,3,5,6,1,3,6,4,9,7,0,8,0,3,9,9],
    [1,4,2,5,8,7,7,0,0,7,1,2,1,2,7,7,7,4],
    [3,9,7,9,5,8,9,5,6,9,8,8,0,1,4,2,8,2],
    [1,5,2,2,2,5,6,3,9,3,1,7,9,6,8,6,8,3],
    [5,7,8,3,8,8,3,9,9,8,1,9,2,5,4,7,7,7],
    [2,3,2,4,8,5,1,7,2,9,5,2,4,2,9,2,8,7],
    [0,1,6,1,1,0,0,6,5,4,3,4,3,7,9,6,1,9],
  ]
)); // 12 * 18

这种时候因为广度优先搜索存储的数据量过大，直接导致堆（内存）溢出。

代码如下。

/**
 * @param {number[][]} grid
 * @return {number}
 */
const minPathSum = (grid) => {
  if (!grid.length) {
    return 0;
  }
  if (grid.length === 1 && grid[0].length === 1) {
    return grid[0][0];
  }
  const M = grid.length;
  const N = grid[0].length;
  let pathList = [
    { path: [[0, 0]], sum: grid[0][0] },
  ];
  let min = Number.MAX_SAFE_INTEGER;
  let flag = true;
  while (flag) {
    const tempPath = [];
    let tempMin = Number.MAX_SAFE_INTEGER;
    console.log('------');
    for (let i = 0; i < pathList.length; i++) {
      const pathLength = pathList[i].path.length; // 获取 path 长度
      const top = pathList[i].path[pathLength - 1]; // 获取数组最后一项
      const [m, n] = top; // 获取横纵坐标
      console.log(m, n, pathList[i]);
      // 向右
      if (grid[m + 1] && grid[m + 1][n] !== undefined) {
        const tempSum = pathList[i].sum + grid[m + 1][n];
        tempPath.push({
          path: [...pathList[i].path, [m + 1, n]],
          sum: tempSum,
        });
        tempMin = Math.min(tempMin, tempSum);
      }
      // 向下
      if (grid[m][n + 1] !== undefined) {
        const tempSum = pathList[i].sum + grid[m][n + 1];
        tempPath.push({
          path: [...pathList[i].path, [m, n + 1]],
          sum: tempSum,
        });
        tempMin = Math.min(tempMin, tempSum);
      }
      // 设置中止条件
      if ((m + 1 === M - 1 && n === N - 1) || (m === M - 1 && n + 1 === N - 1)) {
        flag = false;
      }
    }
    pathList = tempPath;
    min = tempMin;
  }
  return min;
};

// console.log(minPathSum(
//   [
//     [1,3,1],
//     [1,5,1],
//     [4,2,1],
//   ],
// )); // 7
// console.log(minPathSum(
//   [
//     [1,3,1,1,1],
//     [1,5,1,1,1],
//     [4,2,1,1,1],
//   ],
// )); // 9
// console.log(minPathSum(
//   [
//     [0],
//   ],
// )); // 0
console.log(minPathSum(
  [
    [7,1,3,5,8,9,9,2,1,9,0,8,3,1,6,6,9,5],
    [9,5,9,4,0,4,8,8,9,5,7,3,6,6,6,9,1,6],
    [8,2,9,1,3,1,9,7,2,5,3,1,2,4,8,2,8,8],
    [6,7,9,8,4,8,3,0,4,0,9,6,6,0,0,5,1,4],
    [7,1,3,1,8,8,3,1,2,1,5,0,2,1,9,1,1,4],
    [9,5,4,3,5,6,1,3,6,4,9,7,0,8,0,3,9,9],
    [1,4,2,5,8,7,7,0,0,7,1,2,1,2,7,7,7,4],
    [3,9,7,9,5,8,9,5,6,9,8,8,0,1,4,2,8,2],
    [1,5,2,2,2,5,6,3,9,3,1,7,9,6,8,6,8,3],
    [5,7,8,3,8,8,3,9,9,8,1,9,2,5,4,7,7,7],
    [2,3,2,4,8,5,1,7,2,9,5,2,4,2,9,2,8,7],
    [0,1,6,1,1,0,0,6,5,4,3,4,3,7,9,6,1,9],
  ]
)); // 12 * 18

如上，pathList 的趋势为：

------
[ { path: [ [Array] ], sum: 1 } ]
------
[ { path: [ [Array], [Array] ], sum: 2 },
  { path: [ [Array], [Array] ], sum: 4 } ]
------
[ { path: [ [Array], [Array], [Array] ], sum: 3 },
  { path: [ [Array], [Array], [Array] ], sum: 7 },
  { path: [ [Array], [Array], [Array] ], sum: 9 },
  { path: [ [Array], [Array], [Array] ], sum: 5 } ]
------
[ { path: [ [Array], [Array], [Array], [Array] ], sum: 7 },
  { path: [ [Array], [Array], [Array], [Array] ], sum: 8 },
  { path: [ [Array], [Array], [Array], [Array] ], sum: 12 },
  { path: [ [Array], [Array], [Array], [Array] ], sum: 9 },
  { path: [ [Array], [Array], [Array], [Array] ], sum: 14 },
  { path: [ [Array], [Array], [Array], [Array] ], sum: 11 },
  { path: [ [Array], [Array], [Array], [Array] ], sum: 7 },
  { path: [ [Array], [Array], [Array], [Array] ], sum: 6 } ]
------
[... 6846379 more items ]

所以，为了解决这个问题，势必要进行优化：

/**
 * @param {number[][]} grid
 * @return {number}
 */
const minPathSum = (grid) => {
  if (!grid.length) {
    return 0;
  }
  const M = grid.length;
  const N = grid[0].length;
  for (let i = 0; i < M; i++) {
    for (let j = 0; j < N; j++) {
      // 从 [0, 0] 触发
      if (i === 0 && j === 0) {
        continue;
      }
      // 如果上左都存在，取两者最小
      if (grid[i - 1] && grid[i - 1][j] !== undefined && grid[i][j - 1] !== undefined) {
        grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
      } else if (grid[i - 1] && grid[i - 1][j] !== undefined) { // 如果只存在上
        grid[i][j] += grid[i - 1][j];
      } else if (grid[i][j - 1] !== undefined) { // 如果只存在左
        grid[i][j] += grid[i][j - 1];
      }
    }
  }
  return grid[M - 1][N - 1];
};

因为广度搜索要排出的机器人太多了，走的路线连 JavaScript 都存储不过来。

所以只能将每次结果最优存储起来，最终找出剩下的结果 grid[M - 1][N - 1]。

四统计分析

本题不需要统计分析。

五套路分析

本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。

jsliang 的文档库由梁峻荣采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

leetcode-最小路径和

最小路径和

二 题目

三 解题思路

四 统计分析

五 套路分析

二题目

三解题思路

四统计分析

五套路分析