自学内容网 自学内容网

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

前言

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

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

题目描述

在这里插入图片描述

基本思路

1. 问题定义:

给定一个 m × n m \times n m×n 的网格,每个单元格包含一个非负整数,表示从起点 ( θ , θ ) (\theta, \theta) (θ,θ) 到终点 ( m − 1 , n − 1 ) (m-1, n-1) (m1,n1)的路径的代价。你可以仅向右或向下移动。我们的目标是找到一条路径, 使得路径上的数字之和最小。

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

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

  • 如果当前位置为 ( i , j ) (i, j) (i,j) ,则其最小路径和可以表示为:

d p [ i ] [ j ] = grid ⁡ [ i ] [ j ] + min ⁡ ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) \mathrm{dp}[i][j]=\operatorname{grid}[i][j]+\min (\mathrm{dp}[i-1][j], \mathrm{dp}[i][j-1]) dp[i][j]=grid[i][j]+min(dp[i1][j],dp[i][j1])

其中, dp [ i ] [ j ] [i][j] [i][j] 表示到达 ( i , j ) \mathrm{i}, \mathrm{j}) i,j) 的最小路径和。

3. 解决方法:

3.1. 初始化:

我们需要一个二维数组 d p d p dp ,其中 d p [ i ] [ j ] d p[i][j] dp[i][j] 表示到达 ( i , j ) (i, j) (i,j) 的最小路径和。我们可以直接在原始 grid 数组上进行修改,以节省空间。

3.2. 边界条件:

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

d p [ 0 ] [ j ] = d p [ 0 ] [ j − 1 ] + grid ⁡ [ 0 ] [ j ] \mathrm{dp}[0][j]=\mathrm{dp}[0][j-1]+\operatorname{grid}[0][j] dp[0][j]=dp[0][j1]+grid[0][j]

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

d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] + grid ⁡ [ i ] [ 0 ] \mathrm{dp}[i][0]=\mathrm{dp}[i-1][0]+\operatorname{grid}[i][0] dp[i][0]=dp[i1][0]+grid[i][0]

3.3. 填充 dp 数组:

( 1 , 1 ) (1,1) (1,1) 开始填充 dp 数组,直到 ( m − 1 , n − 1 ) (m-1, n-1) (m1,n1)

3.4. 返回结果:

d p [ m − 1 ] [ n − 1 ] dp [m-1][n-1] dp[m1][n1] 即为所求的最小路径和。

4. 进一步优化:

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

  • 时间复杂度: O ( m ∗ n ) O(m * n) O(mn) ,需要遍历整个网格。
  • 空间复杂度:使用 O ( n ) O(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 代码解释

  • 边界条件:检查输入是否为空。
  • 初始化:创建一维数组 d p dp dp 来存储当前行的最小路径和。
  • 动态规划:先初始化第一行的值,然后逐行更新 d p dp dp 数组中的值,最终返回右下角的值。

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();
    }
};

C++ 代码解释

  • 边界条件:检查输入是否为空。
  • 初始化:使用一维数组 dp 来存储当前行的最小路径和。
  • 动态规划:初始化第一行的值,并逐行更新 dp 数组,最终返回右下角的最小路径和。

总结:

  1. 动态规划是解决最小路径和问题的有效方法,通过构建状态转移方程和动态更新路径和来求解最优解。
  2. 空间优化:使用一维数组来降低空间复杂度,使算法在时间和空间上都更高效。

原文地址:https://blog.csdn.net/AlbertDS/article/details/142585447

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!