Medium

题目描述

给定一个 n x n 的整数矩阵 matrix，返回通过矩阵的任何下降路径的最小和。

下降路径 从第一行的任何元素开始，并选择下一行中直接位于下方或对角线左/右的元素。具体来说，从位置 (row, col) 的下一个元素将是 (row + 1, col - 1)、(row + 1, col) 或 (row + 1, col + 1)。

示例 1：

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：如图所示，有两条和最小的下降路径。

示例 2：

输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：如图所示，和最小的下降路径。

提示：

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 100
  • -100 <= matrix[i][j] <= 100

解题思路

这是一个经典的动态规划问题，可以用多种方法求解：

方法一：自上而下的动态规划（推荐）

  • 状态定义：dp[i][j] 表示从第一行到达位置 (i, j) 的最小路径和
  • 状态转移：dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])
  • 边界处理：注意处理列索引越界的情况
  • 最终答案：min(dp[n-1][j]) for all j

方法二：原地修改优化

  • 直接在原矩阵上进行修改，节省空间复杂度
  • 每个位置存储到达该位置的最小路径和

方法三：滚动数组优化

  • 由于只需要上一行的信息，可以用一维数组优化空间

本解答采用原地修改的方法，既简洁又高效。从第二行开始，每个位置的值更新为到达该位置的最小路径和，最后返回最后一行的最小值即可。

代码实现

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int minPrev = matrix[i-1][j];
                if (j > 0) {
                    minPrev = min(minPrev, matrix[i-1][j-1]);
                }
                if (j < n-1) {
                    minPrev = min(minPrev, matrix[i-1][j+1]);
                }
                matrix[i][j] += minPrev;
            }
        }
        
        return *min_element(matrix[n-1].begin(), matrix[n-1].end());
    }
};

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        
        for i in range(1, n):
            for j in range(n):
                min_prev = matrix[i-1][j]
                if j > 0:
                    min_prev = min(min_prev, matrix[i-1][j-1])
                if j < n-1:
                    min_prev = min(min_prev, matrix[i-1][j+1])
                matrix[i][j] += min_prev
        
        return min(matrix[n-1])

public class Solution {
    public int MinFallingPathSum(int[][] matrix) {
        int n = matrix.Length;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int minPrev = matrix[i-1][j];
                if (j > 0) {
                    minPrev = Math.Min(minPrev, matrix[i-1][j-1]);
                }
                if (j < n-1) {
                    minPrev = Math.Min(minPrev, matrix[i-1][j+1]);
                }
                matrix[i][j] += minPrev;
            }
        }
        
        int result = matrix[n-1][0];
        for (int j = 1; j < n; j++) {
            result = Math.Min(result, matrix[n-1][j]);
        }
        return result;
    }
}

var minFallingPathSum = function(matrix) {
    const n = matrix.length;
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < n; j++) {
            let minPrev = matrix[i-1][j];
            if (j > 0) {
                minPrev = Math.min(minPrev, matrix[i-1][j-1]);
            }
            if (j < n-1) {
                minPrev = Math.min(minPrev, matrix[i-1][j+1]);
            }
            matrix[i][j] += minPrev;
        }
    }
    
    return Math.min(...matrix[n-1]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要遍历整个 n×n 矩阵
空间复杂度O(1)原地修改，不使用额外空间

相关题目