LeetCode LCR 099. 最小路径和

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
2. 解法二：动态规划（空间优化）
相似题目

题目描述

✅ LCR 099. 最小路径和

思路分析

解法一：动态规划（推荐）

核心思路：
状态定义：dp[i][j] 表示从左上角 (0,0) 走到 (i,j) 的最小路径和。
转移方程：每个位置只能从上方或左方到达，取两者路径和的较小值再加上当前格权重：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
边界初始化：

起点：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]

结果：dp[m-1][n-1] 即为从左上角到右下角的最小路径和。
复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为矩阵的行数和列数，需遍历整个网格

空间复杂度：O(m × n)，需要一个与网格等大的 dp 数组

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // dp[i][j] 表示从左上角到 (i, j) 的最小路径和
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        // 初始化第一行：只能从左方到达
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        // 初始化第一列：只能从上方到达
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        // 状态转移：取上方和左方的较小值
        for (int i = 1; i < m; i++) {
            for (int 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];
    }
}

func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    // dp[i][j] 表示从左上角到 (i, j) 的最小路径和
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    dp[0][0] = grid[0][0]
    // 初始化第一行：只能从左方到达
    for j := 1; j < n; j++ {
        dp[0][j] = dp[0][j-1] + grid[0][j]
    }
    // 初始化第一列：只能从上方到达
    for i := 1; i < m; i++ {
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }
    // 状态转移：取上方和左方的较小值
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        }
    }
    return dp[m-1][n-1]
}

解法二：动态规划（空间优化）

核心思路：

观察转移方程 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，第 i 行只依赖第 i-1 行（上方）和同行的 j-1 列（左方）。

用一维数组滚动更新：dp[j] 存储当前行第 j 列的最小路径和，从左到右更新时，dp[j] 在更新前代表上方值，dp[j-1] 代表刚更新的左方值。

转移变为：dp[j] = min(dp[j], dp[j-1]) + grid[i][j]

空间从 O(m × n) 降至 O(n)。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为矩阵的行数和列数

空间复杂度：O(n)，其中 n 为矩阵列数，仅使用一维滚动数组

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // 一维 dp 数组，初始化为第一行
        int[] dp = new int[n];
        dp[0] = grid[0][0];
        // 初始化第一行
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j - 1] + grid[0][j];
        }
        // 逐行滚动更新
        for (int i = 1; i < m; i++) {
            // 更新第一列：只能从上方到达
            dp[0] += grid[i][0];
            // 从左到右更新：dp[j] 更新前为上方值，dp[j-1] 为已更新的左方值
            for (int j = 1; j < n; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        return dp[n - 1];
    }
}

func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    // 一维 dp 数组，初始化为第一行
    dp := make([]int, n)
    dp[0] = grid[0][0]
    // 初始化第一行
    for j := 1; j < n; j++ {
        dp[j] = dp[j-1] + grid[0][j]
    }
    // 逐行滚动更新
    for i := 1; i < m; i++ {
        // 更新第一列：只能从上方到达
        dp[0] += grid[i][0]
        // 从左到右更新：dp[j] 更新前为上方值，dp[j-1] 为已更新的左方值
        for j := 1; j < n; j++ {
            dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
        }
    }
    return dp[n-1]
}

相似题目

题目	难度	考察点
62. 不同路径	中等	网格路径计数 DP
63. 不同路径 II	中等	有障碍的网格路径 DP
120. 三角形最小路径和	中等	路径和 DP 变体
174. 地下城游戏	困难	逆向 DP、路径代价
741. 摘樱桃	困难	三维 DP、网格路径
1289. 下降路径最小和 II	困难	路径和 DP
931. 下降路径最小和	中等	路径和 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/63805913