自学内容网 自学内容网

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

前言

在算法的学习中,动态规划是一个至关重要的思想,特别是在解决最优路径问题时,动态规划能够提供一种高效且直观的解决方案。最小下降路径和问题就是这样一个经典的动态规划问题。它要求我们在一个二维矩阵中,从第一行的任意一个元素开始,每次只能向下、左下、右下移动,找到通往最后一行的最小路径和。这类问题不仅在理论上具有挑战性,同时也在实际生活中的路径规划、图像处理等领域有广泛应用。

本文将通过深入剖析最小下降路径和问题,帮助你掌握该类问题的动态规划思路。我们将从问题的定义和递推公式出发,逐步推导解决方法,并提供优化空间复杂度的技巧。同时,本文提供了详细的 Python 和 C++ 代码实现,并对代码进行了逐行解释。无论你是初学者还是有经验的开发者,都可以从本文中获得有益的启发,并加深对动态规划的理解。

希望本文能为你提供清晰的思路,帮助你在解决类似问题时更加得心应手。

题目描述

在这里插入图片描述

基本思路

1. 问题定义

给定一个 n n n * n n n 的方形矩阵 matrix,每个位置都包含一个整数。你可以从矩阵的第一行任何一个元素开始,并逐步向下移动到达最后一行。每次移动时,你只能移动到下一行的同一列、左上方一列或右上方一列的位置。要求你找到从第一行移动到最后一行的最小路径和。

2. 理解问题和递推关系

  • 问题的核心是寻找一条从第一行到最后一行的最小路径和,每次移动只能向下、左下或右下移动。
  • 对于任意位置 ( i , j ) (i, j) (i,j) 的最小路径和 d p [ i ] [ j ] d p[i][j] dp[i][j] ,它可以通过前一行的三个可能位置中的最小值来更新:

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

  • 边界处理:如果位置 ( i − 1 , j − 1 ) (i-1, j-1) (i1,j1) 或 ( i − 1 , j + 1 ) i-1, j+1) i1,j+1) 越界, 忽略该位置。

3. 解决方法

3.1 动态规划方法

  1. 创建一个二维数组 d p d p dp ,其中 d p [ i ] [ j ] d p[i][j] dp[i][j] 表示从第一行到达位置 ( i , j ) (i, j) (i,j) 的最小路径和。
  2. 初始化 d p d p dp 的第一行,直接等于 matrix 的第一行。
  3. 从第二行开始,依次计算每个位置的最小路径和,利用前一行的 dp 值填充当前行的 dp 。
  4. 最终结果为 d p [ n − 1 ] d p[n-1] dp[n1] 中的最小值, 即从第一行到达最后一行的最小路径和。

3.2 空间优化的动态规划

  • 可以使用一维数组代替二维数组 d p d p dp 来节省空间。只需要记录当前行和上一行的最小路径和。

4. 进一步优化

4.1 空间复杂度优化

  • 可以仅使用一维数组保存前一行的最小路径和,逐行更新,降低空间复杂度为 O ( n ) O(n) O(n)

5. 小总结

  • 动态规划是解决此类问题的核心。我们可以通过递推公式求解每一行的最小路径和,逐步构建出全局的最优解。
  • 优化后的空间复杂度可以从 O ( n ∧ 2 ) O\left(n^{\wedge} 2\right) O(n2) 降低到 O ( n ) O(n) O(n) ,这对于大规模矩阵的计算更加高效。

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

代码实现

Python3代码实现

class Solution:
    def minFallingPathSum(self, matrix: list[list[int]]) -> int:
        n = len(matrix)
        # 使用动态规划填充dp数组,第一行等于matrix的第一行
        dp = matrix[0][:]
        
        # 从第二行开始
        for i in range(1, n):
            # 创建一个临时数组存储当前行的最小路径和
            new_dp = [0] * n
            for j in range(n):
                # 当前元素可以从上方、左上方或右上方到达
                min_prev = dp[j]
                if j > 0:
                    min_prev = min(min_prev, dp[j - 1])
                if j < n - 1:
                    min_prev = min(min_prev, dp[j + 1])
                # 更新当前元素的最小路径和
                new_dp[j] = matrix[i][j] + min_prev
            dp = new_dp
        
        # 返回最后一行的最小路径和
        return min(dp)

Python 代码解释

  • 初始化:创建 dp 数组,用于存储前一行的最小路径和。初始化为 matrix 第一行的值。
  • 动态规划递推:从第二行开始,逐行更新 dp。每个位置 (i, j) 的最小路径和通过前一行的三个可能位置 ( d p [ i − 1 ] [ j ] 、 d p [ i − 1 ] [ j − 1 ] 、 d p [ i − 1 ] [ j + 1 ] ) (dp[i-1][j]、dp[i-1][j-1]、dp[i-1][j+1]) dp[i1][j]dp[i1][j1]dp[i1][j+1]中最小的值来更新。
  • 返回结果:最终返回 dp 数组中的最小值,即最后一行的最小路径和。

C++代码实现

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 使用dp数组存储前一行的最小路径和
        vector<int> dp(matrix[0]);

        // 从第二行开始
        for (int i = 1; i < n; ++i) {
            vector<int> new_dp(n, 0);  // 当前行的dp数组
            for (int j = 0; j < n; ++j) {
                int min_prev = dp[j];
                if (j > 0) min_prev = min(min_prev, dp[j - 1]);
                if (j < n - 1) min_prev = min(min_prev, dp[j + 1]);
                new_dp[j] = matrix[i][j] + min_prev;
            }
            dp = new_dp;  // 更新dp为当前行的最小路径和
        }

        // 返回最后一行的最小路径和
        return *min_element(dp.begin(), dp.end());
    }
};

C++ 代码解释

  • 初始化:创建 dp 数组,保存前一行的最小路径和,初始值为 matrix 的第一行。
  • 动态规划递推:从第二行开始,逐行计算每个位置的最小路径和,通过前一行的三个可能位置的最小值更新当前行。
  • 返回结果:遍历最后一行的 dp 数组,返回其中的最小值,即最小路径和。

总结:

  • 时间复杂度:无论是 P y t h o n Python Python 代码还是 C + + C++ C++ 代码,时间复杂度都是 O ( n ∧ 2 ) O\left(n^{\wedge} 2\right) O(n2) ,因为我们需要遍历矩阵的每个元素。
  • 空间复杂度:通过使用一维数组来代替二维 d p d p dp 数组,空间复杂度优化为 O ( n ) O(n) O(n) ,显著减少了内存占用。
  • 动态规划思想:该问题可以通过动态规划思想轻松解决,核心在于计算毎一行的最小路径和,并逐步累积到最后一行。

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

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