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

用户9613193

发布于 2026-06-16 20:05:41

270

动态规划—931. 下降路径最小和

前言
题目描述
基本思路
- 1. 问题定义
- 2. 理解问题和递推关系
- 3. 解决方法
- - 3.1 动态规划方法
  - 3.2 空间优化的动态规划
- 4. 进一步优化
- - 4.1 空间复杂度优化
- 5. 小总结
代码实现
- Python3代码实现
- Python 代码解释
- C++代码实现
- C++ 代码解释
总结:

前言

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

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

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

题目描述

基本思路

1. 问题定义

给定一个

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

2. 理解问题和递推关系

问题的核心是寻找一条从第一行到最后一行的最小路径和，每次移动只能向下、左下或右下移动。
对于任意位置

(i, j)

的最小路径和

d p[i][j]

，它可以通过前一行的三个可能位置中的最小值来更新：

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])

边界处理：如果位置

(i-1, j-1)

或 (

i-1, j+1)

越界, 忽略该位置。

3. 解决方法

3.1 动态规划方法

创建一个二维数组

d p

，其中

d p[i][j]

表示从第一行到达位置

(i, j)

的最小路径和。

初始化

d p

的第一行，直接等于 matrix 的第一行。

从第二行开始，依次计算每个位置的最小路径和，利用前一行的 dp 值填充当前行的 dp 。
最终结果为

d p[n-1]

中的最小值, 即从第一行到达最后一行的最小路径和。

3.2 空间优化的动态规划

可以使用一维数组代替二维数组

d p

来节省空间。只需要记录当前行和上一行的最小路径和。

4. 进一步优化

4.1 空间复杂度优化

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

O(n)

。

5. 小总结

动态规划是解决此类问题的核心。我们可以通过递推公式求解每一行的最小路径和，逐步构建出全局的最优解。
优化后的空间复杂度可以从

O\left(n^{\wedge} 2\right)

降低到

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) 的最小路径和通过前一行的三个可能位置

（dp[i-1][j]、dp[i-1][j-1]、dp[i-1][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());
    }
};