Hard

题目描述

给你一个 n x n 整数矩阵 grid，请你返回 非零偏移下降路径 数字和的最小值。

非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个元素，且按顺序选出来的元素中，相邻行选出的元素不在同一列。

示例 1：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：13
解释：
可能的下降路径有：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7]，所以答案是 13 。

示例 2：

输入：grid = [[7]]
输出：7

提示：

  • n == grid.length == grid[i].length
  • 1 <= n <= 200
  • -99 <= grid[i][j] <= 99

解题思路

这是一道动态规划优化问题。核心在于如何高效处理"相邻行不能选择同一列"的约束。

基本思路： 使用 dp[i][j] 表示到第 i 行第 j 列的最小路径和。状态转移方程为： dp[i][j] = grid[i][j] + min(dp[i-1][k]) (其中 k ≠ j)

朴素解法： 时间复杂度 O(n³)，对每个位置遍历上一行所有不同列的元素。

优化思路： 观察到对于每一行，我们只需要知道上一行的两个信息：

  1. 最小值及其列索引
  2. 次小值（当前列恰好是最小值所在列时使用）

这样可以将时间复杂度优化到 O(n²)。

算法步骤：

  1. 初始化第一行的 dp 值
  2. 对于每一行，维护上一行的最小值和次小值
  3. 根据当前列是否为最小值所在列，选择对应的值进行状态转移
  4. 更新当前行的最小值和次小值信息
  5. 返回最后一行的最小值

代码实现

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        if (n == 1) return grid[0][0];
        
        vector<int> dp(n);
        for (int j = 0; j < n; j++) {
            dp[j] = grid[0][j];
        }
        
        for (int i = 1; i < n; i++) {
            // 找到上一行的最小值和次小值
            int min1 = INT_MAX, min2 = INT_MAX;
            int minIdx = -1;
            
            for (int j = 0; j < n; j++) {
                if (dp[j] < min1) {
                    min2 = min1;
                    min1 = dp[j];
                    minIdx = j;
                } else if (dp[j] < min2) {
                    min2 = dp[j];
                }
            }
            
            vector<int> newDp(n);
            for (int j = 0; j < n; j++) {
                if (j == minIdx) {
                    newDp[j] = grid[i][j] + min2;
                } else {
                    newDp[j] = grid[i][j] + min1;
                }
            }
            dp = newDp;
        }
        
        return *min_element(dp.begin(), dp.end());
    }
};

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 1:
            return grid[0][0]
        
        dp = grid[0][:]
        
        for i in range(1, n):
            # 找到上一行的最小值和次小值
            min_vals = sorted(enumerate(dp), key=lambda x: x[1])
            min1_idx, min1_val = min_vals[0]
            min2_val = min_vals[1][1]
            
            new_dp = [0] * n
            for j in range(n):
                if j == min1_idx:
                    new_dp[j] = grid[i][j] + min2_val
                else:
                    new_dp[j] = grid[i][j] + min1_val
            
            dp = new_dp
        
        return min(dp)

public class Solution {
    public int MinFallingPathSum(int[][] grid) {
        int n = grid.Length;
        if (n == 1) return grid[0][0];
        
        int[] dp = new int[n];
        for (int j = 0; j < n; j++) {
            dp[j] = grid[0][j];
        }
        
        for (int i = 1; i < n; i++) {
            // 找到上一行的最小值和次小值
            int min1 = int.MaxValue, min2 = int.MaxValue;
            int minIdx = -1;
            
            for (int j = 0; j < n; j++) {
                if (dp[j] < min1) {
                    min2 = min1;
                    min1 = dp[j];
                    minIdx = j;
                } else if (dp[j] < min2) {
                    min2 = dp[j];
                }
            }
            
            int[] newDp = new int[n];
            for (int j = 0; j < n; j++) {
                if (j == minIdx) {
                    newDp[j] = grid[i][j] + min2;
                } else {
                    newDp[j] = grid[i][j] + min1;
                }
            }
            dp = newDp;
        }
        
        return dp.Min();
    }
}

var minFallingPathSum = function(grid) {
    const n = grid.length;
    let dp = [...grid[0]];
    
    for (let i = 1; i < n; i++) {
        const newDp = new Array(n).fill(Infinity);
        
        for (let j = 0; j < n; j++) {
            for (let k = 0; k < n; k++) {
                if (j !== k) {
                    newDp[j] = Math.min(newDp[j], dp[k] + grid[i][j]);
                }
            }
        }
        
        dp = newDp;
    }
    
    return Math.min(...dp);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²) - 外层循环 n 次，内层每次遍历 n 个元素找最小值和次小值
空间复杂度O(n) - 使用一维数组存储 dp 状态

相关题目