#64. 最小路径和

• LeetCode 64 原题链接
• LCR 099 原题链接

#题目描述

给定一个包含非负整数的 m × n 网格 grid，从左上角出发，每次只能向右或向下移动一步，求到达右下角时经过数字之和最小的路径。

路径和需要包含起点和终点的数字。

示例：

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

输入：grid = [[1,2,3],
              [4,5,6]]
输出：12
解释：最小路径为 1 -> 2 -> 3 -> 6。

#1. 为什么使用动态规划

对于任意格子 (i, j)，因为只能向右或向下移动，所以到达它的最后一步只有两种来源：

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

如果已经知道到达上方和左侧的最小路径和，那么只需选择较小者，再加上当前格子的值，就能得到到达当前格子的最小路径和。

问题具有：

• 最优子结构：当前最优解可以由前驱位置的最优解推出。
• 重复子问题：递归搜索时，同一个格子的最小路径和会被多次计算。

因此适合使用动态规划。

#2. 状态定义

定义：

dp[i][j]：从左上角 (0, 0) 走到格子 (i, j) 的最小路径和

根据这个定义，最终答案是：

dp[m - 1][n - 1]

状态定义必须明确包含当前格子的值，否则初始化和转移时很容易重复加或漏加 grid[i][j]。

#3. 状态转移方程

对于内部格子 (i, j)，上方和左侧都存在：

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

这里取 min，因为题目要求路径和最小；最后再加上进入当前格子必须付出的 grid[i][j]。

这两个来源覆盖了到达当前格子的所有合法路径，而且互不遗漏。

#4. 初始化

#起点

起点没有前驱位置，路径和就是它自身：

dp[0][0] = grid[0][0];

#第一列

第一列中的格子只能从上方到达，因此需要逐行累计：

for (let i = 1; i < m; i++) {
  dp[i][0] = dp[i - 1][0] + grid[i][0];
}

#第一行

第一行中的格子只能从左侧到达，因此需要逐列累计：

for (let j = 1; j < n; j++) {
  dp[0][j] = dp[0][j - 1] + grid[0][j];
}

第一行和第一列不能像「不同路径」那样全部初始化为 1。本题保存的是路径和，而不是路径数量，边界状态必须累计沿途经过的网格值。

#5. 遍历顺序

计算 dp[i][j] 时需要：

dp[i - 1][j]：上一行已经计算完成
dp[i][j - 1]：当前行左侧已经计算完成

因此应按从上到下、从左到右的顺序遍历：

for (let i = 1; i < m; i++) {
  for (let j = 1; j < n; j++) {
    // 更新 dp[i][j]
  }
}

#6. 示例推演

对于：

grid = 1  3  1
       1  5  1
       4  2  1

初始化起点、第一行和第一列：

dp = 1  4  5
     2  0  0
     6  0  0

继续计算内部格子：

dp[1][1] = min(4, 2) + 5 = 7
dp[1][2] = min(5, 7) + 1 = 6
dp[2][1] = min(7, 6) + 2 = 8
dp[2][2] = min(6, 8) + 1 = 7

最终 DP 表：

1  4  5
2  7  6
6  8  7

右下角的 dp[2][2] = 7，所以最小路径和为 7。

注意，dp[i][j] 只保存最小路径和，并没有保存具体路径。示例中的最优路径可以通过从终点反向比较前驱状态恢复。

#7. 二维动态规划实现

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

  dp[0][0] = grid[0][0];

  for (let i = 1; i < m; i++) {
    dp[i][0] = dp[i - 1][0] + grid[i][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++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
  }

  return dp[m - 1][n - 1];
};

#8. 使用哨兵统一边界处理

也可以额外创建一行一列，把越界位置初始化为 Infinity：

var minPathSum = function (grid) {
  const m = grid.length;
  const n = grid[0].length;
  const dp = Array.from(
    { length: m + 1 },
    () => new Array(n + 1).fill(Infinity),
  );

  dp[0][1] = 0;

  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]) + grid[i - 1][j - 1];
    }
  }

  return dp[m][n];
};

这里实际网格 (0, 0) 对应 DP 表中的 (1, 1)。人工设置：

dp[0][1] = 0;

可以让起点通过统一公式得到：

dp[1][1] = min(dp[0][1], dp[1][0]) + grid[0][0]
         = min(0, Infinity) + grid[0][0]
         = grid[0][0]

越界位置必须使用 Infinity，不能使用 0。如果使用 0，Math.min 会把不存在的越界路径误认为更优路径，导致第一行和第一列无法正确累计。

这与「不同路径」中的 dp[0][1] = 1 思路相同：哨兵值由转移运算的单位元决定。

• 路径计数使用加法，入口值设为 1。
• 最小路径和使用取最小值再加权，入口值设为 0，其他非法来源设为 Infinity。

#9. 一维数组空间优化

当前行只依赖上一行和当前行左侧，因此可以使用一维数组。

更新 dp[j] 前：

dp[j] 表示上方格子的最小路径和

更新 dp[j - 1] 后：

dp[j - 1] 表示当前行左侧格子的最小路径和

代码如下：

var minPathSum = function (grid) {
  const m = grid.length;
  const n = grid[0].length;
  const dp = new Array(n).fill(Infinity);

  dp[0] = 0;

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (j === 0) {
        dp[j] = dp[j] + grid[i][j];
      } else {
        dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
      }
    }
  }

  return dp[n - 1];
};

遍历必须从左向右进行，确保 dp[j - 1] 已经表示当前行，而 dp[j] 在更新前仍表示上一行。

#10. 原地动态规划

如果允许修改输入，可以直接把 grid 当作 DP 表：

var minPathSum = function (grid) {
  const m = grid.length;
  const n = grid[0].length;

  for (let i = 1; i < m; i++) {
    grid[i][0] += grid[i - 1][0];
  }

  for (let j = 1; j < n; j++) {
    grid[0][j] += grid[0][j - 1];
  }

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

  return grid[m - 1][n - 1];
};

这种写法的额外空间复杂度是 O(1)，但会覆盖原始网格。面试时应主动说明这个副作用；如果调用方仍需要原始输入，应使用独立 DP 数组。

#11. 正确性说明

可以按照遍历顺序进行归纳证明：

1. 起点 dp[0][0] = grid[0][0] 显然正确。
2. 第一行和第一列都只有唯一走法，累计沿途网格值即可得到最小路径和。
3. 假设当前格子的上方和左侧状态都已经正确。任何到达当前格子的合法路径，最后一步必然来自这两个位置之一。选择两者中较小的路径和，再加当前格子的值，就得到所有合法路径中的最小值。

因此每个 dp[i][j] 都符合状态定义，最终的 dp[m - 1][n - 1] 就是答案。

#12. 复杂度分析

一维 DP 还可以选择较短的维度作为数组长度，把空间复杂度进一步写为 O(min(m, n))，但需要相应调整遍历方向和网格访问方式。

#13. 边界条件与易错点

边界条件：

• 只有一个格子时，答案就是 grid[0][0]。
• 只有一行时，只能一直向右，答案是该行所有元素之和。
• 只有一列时，只能一直向下，答案是该列所有元素之和。
• 网格元素可以为 0，不能用“值是否为 0”判断状态是否已经计算。

易错点：

• 路径和必须包含起点与终点。
• 第一行和第一列只有一个前驱，不能直接套用有两个前驱的转移式而不处理越界。
• 不合法的前驱在最小值问题中应视为 Infinity，不能设为 0。
• 一维压缩必须从左向右更新，否则会破坏状态依赖关系。
• 原地 DP 会修改输入，使用前要确认题目或调用方是否允许。
• 本题只能向右或向下，不能从右侧或下方转移过来。

#14. 面试追问

#为什么本题不能使用贪心，每次走向数值更小的相邻格子？

当前较小的格子不代表后续路径和更小。局部选择可能进入一片代价很高的区域，而暂时较大的格子后面可能连接大量 0。动态规划比较的是到达每个位置的完整累计代价，能够保留全局最优性。

#如果需要返回具体路径怎么办？

可以在计算 DP 时额外记录每个格子的最优前驱，最后从右下角反向回溯到左上角；也可以保留完整 DP 表，从终点开始每次走向上方和左侧中 DP 值较小的位置。若两者相等，则可能存在多条最优路径。

#如果网格中存在障碍物怎么办？

把障碍格视为不可达状态，其 DP 值设为 Infinity，其他格子继续从可达的上方和左侧取最小值。如果终点最终仍为 Infinity，说明不存在合法路径。

#如果允许向四个方向移动怎么办？

此时状态依赖可能形成环，不能再简单地按行列顺序做一次 DP。如果边权非负，可以把格子看作图节点，使用 Dijkstra 算法求最短路径。

#15. 可迁移总结

这类网格最值问题可以沿着下面的思路分析：

定义到达当前位置的最优代价
  -> 枚举最后一步的所有合法来源
    -> 取来源中的最优值
      -> 加上进入当前位置的代价

本题最值得迁移的两个细节是：

1. 初始化必须严格服从状态定义，边界格子只有一个合法来源。
2. 最小值问题中的不可达状态应使用 Infinity，避免非法来源被误选为更优解。

掌握这套模型后，可以继续处理带障碍网格、三角形最小路径和、下降路径最小和等问题。