64. 最小路径和

力扣题目链接 (opens new window)

题目描述

给定一个包含非负整数的 m x n 网格 grid,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明: 每次只能向下或者向右移动一步。

示例 1:

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

示例 2:

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

思路

这是一道经典的二维动态规划题目,和 62. 不同路径 非常类似。

动规五部曲

1. 确定 dp 数组及下标含义

dp[i][j] 表示从 (0,0) 到 (i,j) 的最小路径和。

2. 确定递推公式

到达 (i,j) 只有两种方式:

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

那么到达 (i,j) 的最小路径和就是:

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

也就是说,先找到上方和左方的较小值,再加上当前格子的数字。

3. dp 数组初始化

第一行和第一列比较特殊:

• 第一行只能从左边走过来:dp[0][j] = dp[0][j-1] + grid[0][j]
• 第一列只能从上边走过来:dp[i][0] = dp[i-1][0] + grid[i][0]
• 起点:dp[0][0] = grid[0][0]

4. 确定遍历顺序

因为 dp[i][j] 依赖左边和上边的值,所以要从左到右、从上到下遍历。

5. 举例推导 dp 数组

这部分放在"模拟过程"中说明。

模拟过程

以 grid = [[1,3,1],[1,5,1],[4,2,1]] 为例:

初始网格:

1  3  1
1  5  1
4  2  1

第一步:初始化第一行和第一列

第一行:只能一直向右走

dp[0][0] = 1
dp[0][1] = 1 + 3 = 4
dp[0][2] = 4 + 1 = 5

第一列:只能一直向下走

dp[0][0] = 1
dp[1][0] = 1 + 1 = 2
dp[2][0] = 2 + 4 = 6

当前 dp 数组:

1  4  5
2  ?  ?
6  ?  ?

第二步:填充 dp[1][1]

dp[1][1] 可以从上方(dp[0][1]=4)或左方(dp[1][0]=2)到达:

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

第三步:填充 dp[1][2]

dp[1][2] 可以从上方(dp[0][2]=5)或左方(dp[1][1]=7)到达:

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

当前 dp 数组:

1  4  5
2  7  6
6  ?  ?

第四步:填充 dp[2][1]

dp[2][1] 可以从上方(dp[1][1]=7)或左方(dp[2][0]=6)到达:

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

第五步:填充 dp[2][2]

dp[2][2] 可以从上方(dp[1][2]=6)或左方(dp[2][1]=8)到达:

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

最终 dp 数组:

1  4  5
2  7  6
6  8  7

答案是 dp[2][2] = 7,路径为 1→3→1→1→1。

drawio 提示词: 画两张图展示 DP 过程。第一张展示 3×3 网格,标注初始化后的第一行和第一列的累加值,用箭头表示"只能向右"和"只能向下"。第二张展示逐格填充的过程,选取 dp[1][1]、dp[1][2]、dp[2][2] 三个关键格子,每个格子旁边标注"min(上,左)+当前值"的计算过程和箭头指向。两张图画布统一,Logo 放左下角。

文件名:

• 0064.minimum-path-sum-01-initialization.drawio
• 0064.minimum-path-sum-02-dp-fill.drawio

解题代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // 初始化起点
        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] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        
        return dp[m-1][n-1];
    }
};

复杂度分析

• 时间复杂度:O(m×n),需要填充整个 dp 数组
• 空间复杂度:O(m×n),dp 数组的大小

空间优化

可以直接在原数组 grid 上修改,避免额外空间:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // 初始化第一行
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j-1];
        }
        
        // 初始化第一列
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i-1][0];
        }
        
        // 填充其他位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
            }
        }
        
        return grid[m-1][n-1];
    }
};

这样空间复杂度降为 O(1)(不考虑修改原数组)。

其他语言

Python3

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 初始化第一行
        for j in range(1, n):
            grid[0][j] += grid[0][j-1]
        
        # 初始化第一列
        for i in range(1, m):
            grid[i][0] += grid[i-1][0]
        
        # 填充其他位置
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        
        return grid[m-1][n-1]

Java

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        // 初始化第一行
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j-1];
        }
        
        // 初始化第一列
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i-1][0];
        }
        
        // 填充其他位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
            }
        }
        
        return grid[m-1][n-1];
    }
}

Go

func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    
    // 初始化第一行
    for j := 1; j < n; j++ {
        grid[0][j] += grid[0][j-1]
    }
    
    // 初始化第一列
    for i := 1; i < m; i++ {
        grid[i][0] += grid[i-1][0]
    }
    
    // 填充其他位置
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        }
    }
    
    return grid[m-1][n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

JavaScript

var minPathSum = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // 初始化第一行
    for (let j = 1; j < n; j++) {
        grid[0][j] += grid[0][j-1];
    }
    
    // 初始化第一列
    for (let i = 1; i < m; i++) {
        grid[i][0] += grid[i-1][0];
    }
    
    // 填充其他位置
    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];
};

与代码随想录联系

这道题和代码随想录中的 62. 不同路径 是姊妹题。

62 题求的是路径数量,本题求的是路径和的最小值。虽然求的东西不同,但 DP 的思路是一样的:都是"当前位置的最优解 = 上方和左方的最优解推导而来"。

建议录友们把这两道题对比着看,理解二维网格 DP 的通用套路:

1. dp[i][j] 的含义
2. 递推公式(考虑从哪些方向到达)
3. 初始化第一行和第一列
4. 从左到右、从上到下遍历

这个套路在很多网格路径题中都适用,比如:

• 62. 不同路径(求路径数)
• 63. 不同路径 II(有障碍物)
• 64. 最小路径和(求最小和)

掌握了这个模板,类似题目都能快速解决。