LeetCode LCR 099. 最小路径和

约 4 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 动态规划 LCR 矩阵

题目描述

✅ LCR 099. 最小路径和

image-20260929004338593

image-20260929004338596

题意分析

在非负整数网格中，从左上角走到右下角，每次只能向右或向下一格，求经过的数字总和最小的路径。起点和终点的值都要计入。

网格至少有一行一列。本解法将中间结果直接写回 grid，执行后网格保存的是最小路径和，不再是原始格子值。

解法：原地更新最小路径和

核心思路

[!blue]

到达 (row, col) 的最后一步只能来自上方或左方。无论从哪边来，都必须再加上当前格子的值，所以当前最小路径和等于 grid[row][col] + min(上方最小路径和, 左方最小路径和)。两种来源覆盖了全部合法路径，分别保留到达前驱的最优代价就足够了。

第一行没有上方来源，只能从左边一路累加；第一列没有左方来源，只能从上边一路累加。起点保留自身数值，两条边界都从下标 1 开始处理，避免重复累加起点。

初始化边界后，从第二行、第二列开始按行扫描。写入当前格子前，grid[row][col] 仍是原始代价，上方和左方则已经是对应位置的最小路径和。将三者按转移合并后，当前格子也变成一个完成的状态。

后面的格子只需要这里的最优累计代价，不再需要它的原始值，因此覆盖输入是安全的。依赖方向始终朝上或朝左，处理顺序又保证它们先完成，最终右下角保存的就是整条路径的最小和。

解题步骤

  1. 从下标 1 开始累加第一列和第一行。
  2. 从 (1, 1) 开始，按行从左到右遍历其余格子。
  3. 将当前值加上上方、左方累计代价中的较小者，并写回原格子。
  4. 返回 grid[m - 1][n - 1]。

代码实现

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

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

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

        for (int row = 1; row < m; row++) {
            for (int col = 1; col < n; col++) {
                // 当前格子只能从上方或左方到达，取较小路径继续。
                grid[row][col] += Math.min(grid[row - 1][col], grid[row][col - 1]);
            }
        }

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

func minPathSum(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])

    for row := 1; row < m; row++ {
        grid[row][0] += grid[row-1][0]
    }
    for col := 1; col < n; col++ {
        grid[0][col] += grid[0][col-1]
    }

    for row := 1; row < m; row++ {
        for col := 1; col < n; col++ {
            // 当前格子只能从上方或左方到达，取较小路径继续。
            if grid[row-1][col] < grid[row][col-1] {
                grid[row][col] += grid[row-1][col]
            } else {
                grid[row][col] += grid[row][col-1]
            }
        }
    }

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

复杂度分析

  • 时间复杂度：$O(mn)$，每个格子最多更新一次。
  • 空间复杂度：$O(1)$，复用输入网格保存状态。

关键点总结

[!green]

  • 比较的是到达前驱的完整路径代价，不能只比较下一格的数值。
  • 首行和首列只有一个来源，必须先累计成有效状态。
  • 单行或单列输入只需边界累加；只有一个格子时，直接返回起点值。

易错点总结

[!yellow]

  • 未累加首行首列，就会把单个格子值误当成完整的前缀路径和。
  • 转移只写入前驱最小值而不加当前值，会漏算当前格子的代价。
  • 从右下向左上更新却仍读取上方、左方，会读到尚未计算的原始值。
  • 按眼前较小的相邻格子贪心前进，无法保证后续总和最小。
  • 终点下标是 (m - 1, n - 1)，不是 (m, n)。

相似题目

题目 难度 关联与区别
62. 不同路径 中等 移动方向相同，原题累计路径条数，本题对两个前驱取最小值并加当前格代价。
120. 三角形最小路径和 中等 同样逐层求最小路径和，三角形的前驱或后继位置规则与矩形网格不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/63805913
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！