问题描述

leetcode原题：https://leetcode.cn/problems/minimum-path-sum/description/

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

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

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

思路解析

1. 使用动态规划思路，从 1 * 1, 2*2, 2 * 3, ..., m * n 考虑各个子矩阵的最小路径和，路径和为 sum[m, n] = min(sum(m-1, n) + sum(m, n -1)) + grid[m][n]
2. 使用BFS遍历方式，遍历所有路径，计算最小值，每一个路径都需要保存对应的值

代码实现

1. 动态规划

/**
 * 最小路径和
 * 1, 1, 3
 * 1, 5, 1
 * 4, 2, 1
 * @nums Array<Array>, 
 */
function minPathSum(nums) {
  const m = nums.length;
  const n = nums[0].length;

  const dp = new Array(m);
  
  for(let i = 0; i < m; i++) {
    if (!dp[i]) {
      dp[i] = [];
    }
    if (i === 0) {
      dp[i][0] = nums[i][0];
    } else {
      dp[i][0] = dp[i-1][0] + nums[i][0];
    }
  }
  for (let j = 1; j < n; j++) {
    dp[0][j] = dp[0][j-1] + nums[0][j];
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + nums[i][j];
    }
  }
  return dp[m-1][n-1];
}

2. 基于BFS思路遍历

/**
 * 最小路径和
 * 1, 1, 3
 * 1, 5, 1
 * 4, 2, 1
 * @nums Array<Array>, 
 */
function minPathSum(nums) {
    let min = Infinity;
    // queue中保存的每一个路径中终点的位置信息，该路径已经遍历过的sum
    let queue = [[0, 0, 0]];
    const m = nums.length - 1;
    const n = nums[0].length - 1;

    while (queue.length) {
        const [i, j, preSum] = queue.pop();

        const cur = nums[i][j];
        const curSum = cur + preSum;
        if (i === n && j === m) {
            min = Math.min(min, curSum);
            continue;
        }
        // 向下遍历
        if (i + 1 <= m) {
            queue.push([i + 1, j, curSum]);
        }
        // 向右遍历
        if (j + 1 <= n) {
            queue.push([i, j + 1, curSum]);
        }
    }
    return min;
}

测试用例

console.log(minPathSum([[1,1,3], [1,5,1], [4,2,1]])); // 7
console.log(minPathSum([[3,7,3,2,5], [1,5,1,4,3], [4,2,1,3,3]])); // 17
console.log(minPathSum([[3,7,3,2,5], [1,5,1,4,3], [4,2,1,7,3]])); // 20