1. 题目描述

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

示例 1：
64. 最小路径和 - 图1

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

示例 2：

  1. 输入：grid = [[1,2,3],[4,5,6]]
  2. 输出：12

提示：

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

    2. 解题思路

    对于这道题目，路径的方向只能是从上到下，从左向右。我们可以知道，当前点的路径和都和上一个点的路径和相关，所以这里我们可以使用动态规划来解答。

对于第一行的元素，它只能是左边的元素移动过来的，当前的元素的路径总和关系如下：

  1. grid[i][0] += grid[i - 1][0]

对于第一列的元素，它只能是上边的元素移动过来的，当前的元素的路径总和关系如下：

  1. grid[0][j] += grid[0][j - 1]

对于其他位置的元素，他可以是上边移动过来的，也可以是左边移动过来的，因为要求的是最小路径和，所以我们只需要选取左边和上面的路径和最小值，当前的元素的路径总和关系如下：

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

这样，经过遍历之后，每个节点的值就是当前的最小路径和。最后只需要返回右下角元素的值即可。

复杂度分析：

  • 时间复杂度：O(mn)，其中 m 和 n 分别是网格的行数和列数。需要对整个网格遍历一次，计算 grid 的每个元素的值。

  • 空间复杂度：O(1)，这里我们是在原数组的基础上进行的操作，所需的额外的空间为常数。

    3. 代码实现

    1. /**
    2. * @param {number[][]} grid
    3. * @return {number}
    4. */
    5. var minPathSum = function(grid) {
    6.   let m = grid.length, n = grid[0].length
    8.   for(let i = 1; i < m; i++){
    9.       grid[i][0] += grid[i - 1][0]
    10.   }
    11.   for(let j = 1; j < n; j++){
    12.       grid[0][j] += grid[0][j - 1]
    13.   }
    15.   for(let i = 1; i < m; i++){
    16.       for(let j = 1; j < n; j++){
    17.           grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
    18.       }
    19.   }
    20.   return grid[m - 1][n - 1]
    21. }

    4. 提交结果

    image.png