力扣931题最小下降路径和解析 动态规划解法 LeetCode解题技巧

一、题目解读

力扣931题「Minimum Falling Path Sum」（最小下降路径和）要求在一个n x n的整数矩阵中，计算从顶部到底部的最小路径和。路径只能从每个位置向下或对角线移动（即向下、左下、右下）。题目关键在于如何通过路径选择优化，找到全局最小值。

二、解题思路

采用动态规划（Dynamic Programming）自底向上递推的策略。核心思想是从矩阵倒数第二行开始，逐行计算每个位置的最小下降路径和。通过记录当前位置到末尾的最小路径和，避免重复计算，最终得到全局最优解。

三、解题步骤

1. 边界处理：判断矩阵是否为空，空矩阵直接返回0。

2. 递推计算：

    从倒数第二行（i = n-2）开始逆向遍历至第一行。

    对每行每个位置j，计算下一行相邻位置（j-1、j、j+1）中的最小值min_val。

    将min_val累加至当前位置：matrix[i][j] += min_val，更新当前路径和。

3. 结果获取：遍历第一行，返回其中的最小值。

四、代码与注释

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

五、总结

该解法通过动态规划将O(n^3)的暴力枚举优化至O(n^2)，空间复杂度仅为O(1)（原地修改矩阵）。关键在于利用“最优子结构”性质，自底向上递推避免了重复计算。对于类似需要路径优化的题目，动态规划是核心解题思路。

参考：C++算法