【LeetCode】动态规划—最小路径和（附完整Python/C++代码）

用户9613193

发布于 2026-06-16 20:06:22

640

动态规划—64. 最小路径和

前言
题目描述
基本思路
- 1. 问题定义:
- 2. 理解问题和递推关系:
- 3. 解决方法:
- - 3.1. 初始化:
  - 3.2. 边界条件:
  - 3.3. 填充 dp 数组:
  - 3.4. 返回结果:
- 4. 进一步优化:
- 5. 小总结:
代码实现
- Python3代码实现
- Python 代码解释
- C++代码实现
- C++ 代码解释
总结:

前言

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

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

题目描述

基本思路

1. 问题定义:

给定一个

m \times n

的网格，每个单元格包含一个非负整数，表示从起点

(\theta, \theta)

到终点

(m-1, n-1)

的路径的代价。你可以仅向右或向下移动。我们的目标是找到一条路径, 使得路径上的数字之和最小。

2. 理解问题和递推关系:

在这个问题中，我们需要考虑如何从左上角移动到右下角。每个位置的最小路径和可以通过其上方或左方的路径和来计算:

如果当前位置为

(i, j)

，则其最小路径和可以表示为:

\mathrm{dp}[i][j]=\operatorname{grid}[i][j]+\min (\mathrm{dp}[i-1][j], \mathrm{dp}[i][j-1])

其中， dp

[i][j]

表示到达 (

\mathrm{i}, \mathrm{j})

的最小路径和。

3. 解决方法:

3.1. 初始化:

我们需要一个二维数组

d p

，其中

d p[i][j]

表示到达

(i, j)

的最小路径和。我们可以直接在原始 grid 数组上进行修改，以节省空间。

3.2. 边界条件:

第一行的路径和只能从左边过来, 因此:

\mathrm{dp}[0][j]=\mathrm{dp}[0][j-1]+\operatorname{grid}[0][j]

第一列的路径和只能从上边过来, 因此:

\mathrm{dp}[i][0]=\mathrm{dp}[i-1][0]+\operatorname{grid}[i][0]

3.3. 填充 dp 数组:

从

(1,1)

开始填充 dp 数组，直到

(m-1, n-1)

。

3.4. 返回结果:

dp [m-1][n-1]

即为所求的最小路径和。

4. 进一步优化:

由于计算每个位置的最小路径和仅依赖于上方和左方的位置，我们可以使用一维数组代替二维数组，从而降低空间复杂度。

时间复杂度:

O(m * n)

，需要遍历整个网格。

空间复杂度：使用

O(n)

的空间来存储当前行的路径和。

5. 小总结:

动态规划: 通过构建一个 dp 数组，记录每个位置的最小路径和，最终得到从起点到终点的最小路径和。
空间优化: 可以用一维数组来存储当前行的最小路径和，进一步降低空间复杂度。

以上就是最小路径和问题的基本思路。

代码实现

Python3代码实现

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        
        # 用于存储当前行的最小路径和
        dp = [0] * cols
        
        # 初始化第一行
        for j in range(cols):
            dp[j] = grid[0][j] if j == 0 else dp[j-1] + grid[0][j]
        
        # 遍历每一行
        for i in range(1, rows):
            # 初始化当前行的第一列
            dp[0] += grid[i][0]
            # 遍历当前行
            for j in range(1, cols):
                dp[j] = grid[i][j] + min(dp[j], dp[j-1])
        
        # 返回右下角的最小路径和
        return dp[-1]

Python 代码解释

边界条件：检查输入是否为空。
初始化：创建一维数组

来存储当前行的最小路径和。

动态规划：先初始化第一行的值，然后逐行更新

数组中的值，最终返回右下角的值。

C++代码实现

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        
        int rows = grid.size();
        int cols = grid[0].size();
        
        // 用于存储当前行的最小路径和
        vector<int> dp(cols, 0);
        
        // 初始化第一行
        for (int j = 0; j < cols; ++j) {
            dp[j] = grid[0][j] + (j > 0 ? dp[j - 1] : 0);
        }
        
        // 遍历每一行
        for (int i = 1; i < rows; ++i) {
            dp[0] += grid[i][0];  // 当前行的第一列
            
            // 遍历当前行
            for (int j = 1; j < cols; ++j) {
                dp[j] = grid[i][j] + min(dp[j], dp[j - 1]);
            }
        }
        
        // 返回右下角的最小路径和
        return dp.back();
    }
};