LeetCode 64. 最小路径和

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

题目描述

✅ 64. 最小路径和

image-20230311175400564

题意分析

输入一个 $m \times n$ 的非负整数网格，从左上角出发走到右下角，每一步只能向右或向下移动，要求经过的数字总和最小。

「只能向右向下」是最关键的约束：任何一条路径都恰好经过 $m + n - 1$ 个格子，走过的格子不会被再次经过；到达任意格子 (i, j) 的上一步只可能来自上方 (i - 1, j) 或左方 (i, j - 1)。

数据规模是明确信号：$m, n \le 200$，而从左上到右下的不同路径条数是组合数级别的天文数字，逐条枚举必然超时，必须复用中间结果。

边界上：网格至少 $1 \times 1$；单行只能一路向右、单列只能一路向下，路径唯一；起点和终点的值都要计入总和。

解法：原地动态规划

核心思路

到达 (i, j) 只能来自上方或左方，因此该位置的最小路径和为 grid[i][j] + min(grid[i-1][j], grid[i][j-1])。按从左上到右下的顺序计算，并把结果直接写回 grid，即可省去额外状态数组。

解题步骤

  • 累加第一列，它的每个位置只能从上方到达。
  • 累加第一行，它的每个位置只能从左方到达。
  • 从 (1, 1) 开始遍历，当前值加上上方和左方中的较小值。
  • 返回右下角 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)$，结果直接写回输入网格。

关键点总结

  • 状态表示从左上角到当前格子的最小路径和。
  • 第一行和第一列只有一个来源，需要单独累加。
  • 原地更新依赖从左上到右下的遍历顺序。

易错点总结

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

相似题目

题目 难度 考察点
62. 不同路径 中等 同网格模型改求路径条数，转移是求和
63. 不同路径 II 中等 路径计数加障碍物，转移需分类讨论
120. 三角形最小路径和 中等 三角形结构，自底向上可省去边界特判
174. 地下城游戏 困难 必须从终点倒推，正向递推不满足无后效性
688. 骑士在棋盘上的概率 中等 状态多一维步数，转移带概率权重
931. 下降路径最小和 中等 逐行下落，三个来源取最小
1289. 下降路径最小和 II 困难 禁止同列衔接，需维护每行最小与次小值
1301. 最大得分的路径数目 困难 同时维护最优值与方案数两个状态
1594. 矩阵的最大非负积 中等 乘积含负数，需同时维护最大值与最小值
LCR 098. 不同路径 中等 62 题镜像，路径计数模板练习
LCR 099. 最小路径和 中等 本题镜像，可复用同一份代码
LCR 100. 三角形最小路径和 中等 120 题镜像，空间优化的对照练习
剑指 Offer 47. 礼物的最大价值 中等 同模型改求最大值，转移换成取 max