LeetCode 931. 下降路径最小和

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节
标签
数组 动态规划 矩阵

题目描述

✅ 931. 下降路径最小和

image-20260928225332530

image-20260928225332532

image-20260928225332533

题意分析

在 n × n 矩阵中，从第一行任意位置出发，每一步必须进入下一行的同列、左邻列或右邻列，直到最后一行。求沿途所有格子值之和的最小值。起点和终点都不固定，矩阵也可能含负数。

解法：动态规划状态转移

核心思路

[!blue]

处理完某一行后，dp[j] 表示从首行任意位置出发、到达这一行第 j 列的最小路径和，并且已经包含当前格子。到达同一位置后，后续能走的格子完全相同，所以只保留代价最小的路径即可。

当前格子 (i, j) 的前一步只能来自上一行的 j - 1、j、j + 1 列。每条到达当前格子的路径都属于这三类之一，且它们最后都加上同一个 matrix[i][j]，因此从合法前驱中取最小的 dp，再加当前格子值，就得到 next[j]。首尾列只比较没有越界的来源。

首行没有前驱，直接把每个格子的值作为初始 dp，表示选择它作为起点。每行写入新数组 next，等整行算完才替换 dp，保证所有转移始终读取上一行。最后终点可以在任意列，所以答案是末行所有状态的最小值。

解题步骤

  • 复制首行作为 dp，不改动原矩阵。
  • 从第二行开始新建 next，逐列令 best = dp[j]，先使用一定存在的正上方来源。
  • 若左右相邻列存在，再用 dp[j - 1]、dp[j + 1] 更新 best，令 next[j] = best + matrix[i][j]。
  • 完成整行后执行 dp = next。
  • 用 dp[0] 初始化答案，再取末行最小值。n = 1 时无需转移，直接返回唯一格子的值。

代码实现

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[] dp = Arrays.copyOf(matrix[0], n);

        for (int i = 1; i < n; i++) {
            // 新行单独保存，转移始终读取完整的上一行。
            int[] next = new int[n];

            for (int j = 0; j < n; j++) {
                int best = dp[j];

                if (j > 0) {
                    best = Math.min(best, dp[j - 1]);
                }

                if (j + 1 < n) {
                    best = Math.min(best, dp[j + 1]);
                }

                next[j] = best + matrix[i][j];
            }

            // 整行计算完成后再替换旧状态。
            dp = next;
        }

        int answer = dp[0];

        for (int v : dp) {
            answer = Math.min(answer, v);
        }

        return answer;
    }
}

func minFallingPathSum(matrix [][]int) int {
    n := len(matrix)
    dp := make([]int, n)
    copy(dp, matrix[0])

    for i := 1; i < n; i++ {
        // 新行单独保存，转移始终读取完整的上一行。
        next := make([]int, n)
        for j := 0; j < n; j++ {
            best := dp[j]
            if j > 0 && dp[j-1] < best {
                best = dp[j-1]
            }
            if j+1 < n && dp[j+1] < best {
                best = dp[j+1]
            }
            next[j] = best + matrix[i][j]
        }
        // 整行计算完成后再替换旧状态。
        dp = next
    }

    answer := dp[0]
    for _, v := range dp {
        if v < answer {
            answer = v
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n^2)$。每个格子只比较至多三个前驱，最后扫描一行取最小值。
  • 空间复杂度：$O(n)$。只保留上一行和当前行的两个长度为 n 的数组。

关键点总结

[!green]

  • 状态含当前格子值，因此转移只需在前驱代价上再加当前值一次。
  • 同一终点只保留最小代价，不会影响任何后续选择。
  • 起点任意由首行初始化表达，终点任意由末行取最小值表达。

易错点总结

[!yellow]

  • 不能直接从左到右覆盖 dp，否则左上方状态可能已经变成当前行结果。
  • 首尾列不能读取越界的邻列；先用正上方初始化，再按边界补充候选即可。
  • 不要把最小值初始设为 0，否则全正数矩阵会错误得到不存在的零代价路径。
  • 只返回末行某一列，会漏掉以其他列为终点的更优路径。

相似题目

题目 难度 关联与区别
64. 最小路径和 中等 同样自上而下求最小路径和，本题可走下一行的相邻三列，原题只能向右或向下。
1289. 下降路径最小和 II 困难 原题允许下一行除同列外的任意列，需要最小与次小值优化，本题只查局部三列。
62. 不同路径 中等 在网格上从前驱状态递推路径；本题允许来自上一行三个相邻列，该题累加向右向下的路径数。
63. 不同路径 II 中等 在网格上从前驱状态递推路径；本题允许来自上一行三个相邻列，该题遇障碍时清零可达路径。
120. 三角形最小路径和 中等 在网格上从前驱状态递推路径；本题允许来自上一行三个相邻列，该题按三角形相邻位置求最小路径。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/86656014
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！