最小路径和

更新: 7/5/2026 字数: 0 字 时长: 0 分钟

LeetCode 64. Minimum Path Sum

题目描述

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

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

示例：

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

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

约束：，。

思路拆解：从暴力到最优

想法一：暴力递归（自顶向下）

老规矩，先问：要到达终点 (m-1, n-1)，最后一步是从哪来的？

因为只能向右或向下走，所以到达任意格子 (i, j) 的最后一步只有两种可能：

• 从上方 (i-1, j) 向下走一步；
• 从左方 (i, j-1) 向右走一步。

于是「走到 (i,j) 的最小路径和」= grid[i][j] + 「到上方和到左方两者中更小的那个」。

点击展开暴力解法

function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  // 从 (0,0) 走到 (i,j) 的最小路径和
  function dfs(i, j) {
    if (i === 0 && j === 0) return grid[0][0]; // 起点
    if (i < 0 || j < 0) return Infinity;       // 越界不可达
    return grid[i][j] + Math.min(dfs(i - 1, j), dfs(i, j - 1));
  }
  return dfs(m - 1, n - 1);
}

• 时间：，指数级。因为同一个 (i,j) 会被上方、左方的不同路径重复计算无数次。
• 空间：，递归栈深度。

当网格稍大就会超时。

为什么暴力会爆炸？

到达 (i,j) 的值会被它右边和下边的格子分别用到，而它们又会被各自的右、下格子用到……同一个子问题被成倍地重复求解。这正是「重叠子问题」，是动态规划的典型信号——把每个格子只算一次并存下来。

想法二：二维动态规划（自底向上，DP 表）

既然递推关系清晰，我们直接开一张和网格同样大小的表 dp，其中 dp[i][j] 表示「从起点走到 (i,j) 的最小路径和」，从左上到右下依次填。

核心思路

定义状态 → 找递推 → 定边界 → 顺序填表：

1. 状态：dp[i][j] = 从 (0,0) 走到 (i,j) 的最小路径和。
2. 递推：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])——取上方和左方中较小的那个，加上当前格子的值。
3. 边界：
   • 起点 dp[0][0] = grid[0][0]；
   • 第一行只能一路向右：dp[0][j] = dp[0][j-1] + grid[0][j]；
   • 第一列只能一路向下：dp[i][0] = dp[i-1][0] + grid[i][0]。
4. 顺序：从上到下、从左到右填，保证算 dp[i][j] 时上方和左方都已算好。答案是 dp[m-1][n-1]。

想法三：滚动数组优化（最优解）

观察递推式 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])：算第 行时，只用到第 行和当前行左边的值，更早的行再也用不上了。所以不需要整张二维表，用一维数组滚动更新即可，空间从 降到 。

关键点：遍历到 dp[j] 时，dp[j] 里存的还是上一行的值（即 dp[i-1][j]），而 dp[j-1] 已经在本行更新过（即 dp[i][j-1]）——正好就是我们要的两个来源！

动态演示

下面的动画完整演示了对示例网格 [[1,3,1],[1,5,1],[4,2,1]] 的二维 DP 填表全过程——看每个格子如何由「上方」与「左方」的较小者加上自身值算出：

步骤 1 / 10初始化起点

正在填上方来源左方来源最优路径

原网格 grid

1

3

1

1

5

1

4

2

1

DP 表 dp

1

?

?

?

?

?

?

?

?

起点：dp[0][0] = grid[0][0] = 1。

完整代码（JavaScript）

版本 A：二维 DP 表（直观易懂）

/**
 * @param {number[][]} grid
 * @return {number}
 */
function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));

  dp[0][0] = grid[0][0];              // 起点
  for (let j = 1; j < n; j++)         // 第一行：只能从左边来
    dp[0][j] = dp[0][j - 1] + grid[0][j];
  for (let i = 1; i < m; i++)         // 第一列：只能从上边来
    dp[i][0] = dp[i - 1][0] + grid[i][0];

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      // 取上方和左方较小者，加上当前格子的值
      dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[m - 1][n - 1];
}

版本 B：滚动数组（最优， 空间）

/**
 * @param {number[][]} grid
 * @return {number}
 */
function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = new Array(n).fill(0);

  dp[0] = grid[0][0];
  for (let j = 1; j < n; j++) dp[j] = dp[j - 1] + grid[0][j]; // 初始化第一行

  for (let i = 1; i < m; i++) {
    dp[0] += grid[i][0];              // 每行第一列：只能从上方来
    for (let j = 1; j < n; j++) {
      // 此刻 dp[j] 还是上一行值(上方)，dp[j-1] 已是本行值(左方)
      dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
    }
  }
  return dp[n - 1];
}

进阶：原地修改 grid（O(1) 额外空间）

如果允许修改输入网格，可以直接把 grid 本身当作 DP 表，不开任何额外数组，额外空间降为 ：

function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) continue;
      else if (i === 0) grid[i][j] += grid[i][j - 1];          // 第一行
      else if (j === 0) grid[i][j] += grid[i - 1][j];          // 第一列
      else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
    }
  }
  return grid[m - 1][n - 1];
}

代价是破坏了原始输入，面试时需先和面试官确认是否允许。

复杂度分析

设网格为 行 列。

解法	时间复杂度	空间复杂度	说明
暴力递归			大量重叠子问题，会超时
二维 DP 表			每格算一次，需二维数组
滚动数组			只保留一行，最优空间
原地修改 grid			复用输入，破坏原网格

为什么 DP 是 ？ 一共有 个格子，每个格子只需一次常数级的「取 min 再相加」，所以总时间与格子总数成正比，即 。滚动数组把「存整张表」压缩成「只存一行」，空间降到 。

边界与易错点

易错点

1. 第一行和第一列必须单独初始化。它们只有一个来源方向（第一行只能从左、第一列只能从上），如果直接套用 min(上, 左) 会访问到越界或未初始化的格子。这是本题最容易翻车的地方。

2. 别忘了加上起点自身。dp[0][0] = grid[0][0]，不是 0。整条路径包含起点和终点两个端点的值。

3. 填表顺序不能乱。必须保证算 dp[i][j] 时，dp[i-1][j]（上）和 dp[i][j-1]（左）都已经算好，所以要从上到下、从左到右遍历。

4. 滚动数组里 dp[0] 的更新。每进入新的一行，要先执行 dp[0] += grid[i][0]（第一列累加），否则本行第一个格子的「上方来源」会用错。

5. 单行或单列网格。当 或 时，路径唯一，就是整行/整列之和。上面的初始化逻辑天然覆盖了这种情况，无需额外特判。

6. 求的是「和最小」不是「路径本身」。本题只要返回最小和；若面试官追问「输出具体路径」，需要额外记录每个格子是从上还是从左转移来的，再从终点回溯。

简易解题思路（记忆口诀）

「只能向右或向下，每格来自上或左；取俩来源较小者，加上自己填进格。」

拆开记：

口诀	对应操作
只能向右或向下	移动方向限制，决定了来源方向
每格来自上或左	到 (i,j) 的最后一步来自 (i-1,j) 或 (i,j-1)
取俩来源较小者	min(dp[i-1][j], dp[i][j-1])
加上自己填进格	再加 grid[i][j]，得到 dp[i][j]

一句话记住本质：最小路径和 = 每个格子只从「上方、左方」里挑更省的那条路进来，再加上自己——从左上角一路填到右下角。