LeetCode 64. 最小路径和

约 5 分钟
文章信息 23 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 50-100 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 美团 拼多多 小米 百度 网易 快手 滴滴 虾皮 猿辅导 作业帮
标签
数组 动态规划 矩阵

题目描述

✅ 64. 最小路径和

image-20260928194324629

image-20260928194324630

题意分析

给定一个非空网格，每个格子存放非负数。从左上角走到右下角，每步只能向右或向下，求经过格子的最小数值和，起点和终点都要计入。

需要比较的是整条路径的累计代价，不能每次只选相邻格子中数值更小的一个。因为移动方向固定，到达某个格子的前一步只可能来自上方或左方，可以根据这两个位置的最优结果递推。下面将状态直接写回网格，因此会修改输入。

解法：原地动态规划

核心思路

[!blue]

定义到达一个格子的状态为“从左上角走到这里的最小路径和”。除第一行和第一列外，最后一步只有来自上方、来自左方两种可能，因此当前最小路径和等于当前格子的原始代价，加上两个前驱最小路径和中的较小值。

这个转移不会遗漏更优路径：任何到达当前格子的路径都必须经过这两个前驱之一；若到达前驱的那一段不是最优，就可以替换为更小的前缀，而不影响最后一步。因此只保留各前驱的最小累计值就足够，不需要记住所有完整路径。

起点的最小路径和就是它自身的值。第一列只能从上方到达，第一行只能从左方到达，所以分别顺序累加，不能把不存在的另一侧当作代价为零的入口，否则会凭空产生跳过起点的路径。

边界处理好后，按从上到下、每行从左到右的顺序计算内部格子。此时上方和左方已经保存最小累计值，当前格子仍保存自己的原始代价，直接执行 grid[row][col] += min(上方, 左方) 即可，不需要另建状态数组。

每次只依赖已计算的状态，全部处理完后，右下角就表示到达终点的最小路径和。只有一行或一列时，内部循环自然跳过，边界累加已经得到答案；只有一个格子时，直接返回起点值。

解题步骤

  1. 读取行数 m 和列数 n，保持起点值不变。
  2. 从第二行开始累加第一列，使各格保存唯一可行路径的累计和。
  3. 从第二列开始累加第一行。
  4. 从 (1, 1) 开始按行遍历，其原始值加上已更新的上方、左方累计值中的较小者。
  5. 返回右下角 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, n := len(grid), 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]

  • 起点和终点的值都要计入路径和。
  • 未初始化第一行、第一列，会让边界状态错误。
  • 反向遍历时继续读取上方和左方，会读到尚未更新的值。
  • 该实现会修改 grid；调用方需要保留原数据时应先复制。

相似题目

题目 难度 关联与区别
62. 不同路径 中等 移动方向相同，原题累计路径条数，本题对两个前驱取最小值并加当前格代价。
120. 三角形最小路径和 中等 同样逐层求最小路径和，三角形的前驱或后继位置规则与矩形网格不同。
63. 不同路径 II 中等 在网格上从前驱状态递推路径；本题取较小前驱代价再加当前格，该题遇障碍时清零可达路径。
931. 下降路径最小和 中等 在网格上从前驱状态递推路径；本题取较小前驱代价再加当前格，该题允许来自上一行三个相邻列。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/22175405
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！