力扣931题精讲：动态规划解矩阵最小下降路径和（附完整C++代码）

问题描述

给定一个n x n的方形整数数组matrix，找出并返回通过matrix的下降路径的最小和。下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方、左下方或右下方）。

C++解决方案（带详细注释）

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if (n == 0) return 0;
        
        // 从倒数第二行开始向上递推
        for (int i = n - 2; i >= 0; --i) {
            for (int j = 0; j < n; ++j) {
                // 找出下一行相邻三个位置的最小值
                int min_val = matrix[i+1][j];
                if (j > 0) min_val = min(min_val, matrix[i+1][j-1]);
                if (j < n-1) min_val = min(min_val, matrix[i+1][j+1]);
                
                // 累加到当前路径
                matrix[i][j] += min_val;
            }
        }
        
        // 返回第一行中的最小值
        return *min_element(matrix[0].begin(), matrix[0].end());
    }
};

算法分析

1. 时间复杂度：O(n²)，需要遍历矩阵中的每个元素

2. 空间复杂度：O(1)，在原矩阵上直接修改

3. 边界处理：空矩阵直接返回0

优化方向

1. 使用滚动数组可将空间复杂度优化为O(n)

2. 预处理边界条件避免越界判断

3. 并行化处理每行的计算

常见变种问题

1. 输出具体路径而非仅路径和

2. 允许斜对角移动的扩展版本

3. 带障碍物的版本（特定位置不可通过）

学习建议

1. 先尝试递归解法理解问题本质

2. 画出3x3矩阵的计算过程示例

3. 比较与三角形最小路径和问题的异同