LeetCode 1289. 下降路径最小和 II

约 6 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 微软
标签
数组 动态规划 矩阵

题目描述

✅ 1289. 下降路径最小和 II

image-20260929080455336

image-20260929080455448

题意分析

从方阵每一行恰好选择一个元素，要求相邻两行选择的列不同，求全部所选元素之和的最小值。第一行和最后一行的列都不固定。

可以从上一行跳到任意不同列，不局限于左右相邻位置；只约束相邻行，隔了一行后可以再次使用原列。矩阵可能有负数，因此不能简单挑每行独立的最小值后相加。

解法：DP + 维护两小值

核心思路

[!blue]

定义上一行状态 dp[j] 为：从第一行走到上一行第 j 列的最小累计和。当前行第 j 列只能连接上一行列号不等于 j 的状态，因此转移是当前元素加上“排除同列之后的上一行最小值”。

若为每个当前列重新扫描上一行，整张矩阵需要三次方时间。实际上各列只排除一个位置，只需预先保存上一行最小值 min1、它所在的列 minCol，以及排除这个位置后的最小值 min2。

当前列不是 minCol 时，最小前驱合法，直接使用 min1；当前列恰好是 minCol 时，改用 min2。这两个值按位置区分，不要求数值不同：若另外一列也取得相同最小值，min2 就应与 min1 相等，否则会错误放弃同值的合法前驱。

第一行没有前驱，初值就是各列本身。每轮先完整统计旧行的两小值，再建立新行状态，避免混用新旧层。处理到最后一行后，对所有落点取最小值；只有一行时无需转移，直接返回唯一元素。

解题步骤

  1. 将第一行复制为初始 dp。
  2. 处理下一行前扫描全部旧状态，记录最小值、其列号，以及另一个位置上的最小值。
  3. 当前列等于最小值列号时取 min2，其他列取 min1，再加当前格数值写入新状态数组。
  4. 用新状态替换旧状态，继续下一行。
  5. 最后在整行状态中取最小值返回。

代码实现

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        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 = Integer.MAX_VALUE;
            int min2 = Integer.MAX_VALUE;
            int minCol = -1;

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

                if (v < min1) {
                    min2 = min1;
                    min1 = v;
                    minCol = j;
                } else if (v < min2) {
                    // 次小值按位置计算，可以和最小值相等。
                    min2 = v;
                }
            }

            int[] ndp = new int[n];

            for (int j = 0; j < n; j++) {
                // 排除上一行的同列，最小值所在列必须改用次小值。
                int add = j == minCol ? min2 : min1;

                ndp[j] = grid[i][j] + add;
            }

            dp = ndp;
        }

        int answer = dp[0];

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

        return answer;
    }
}

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

    for i := 1; i < n; i++ {
        // 先完整保存上一行的两小值，之后再计算当前行。
        min1, min2 := int(^uint(0)>>1), int(^uint(0)>>1)
        minCol := -1
        for j := 0; j < n; j++ {
            v := dp[j]
            if v < min1 {
                min2 = min1
                min1 = v
                minCol = j
            } else if v < min2 {
                // 次小值按位置计算，可以和最小值相等。
                min2 = v
            }
        }

        ndp := make([]int, n)
        for j := 0; j < n; j++ {
            add := min1
            // 排除上一行的同列，最小值所在列必须改用次小值。
            if j == minCol {
                add = min2
            }
            ndp[j] = grid[i][j] + add
        }
        dp = ndp
    }

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

复杂度分析

  • 时间复杂度：$O(n^2)$，每行只进行一次两小值统计和一次状态更新，每次都是 $O(n)$。
  • 空间复杂度：$O(n)$，同时保存前后两行状态及常数个最小值信息。

关键点总结

[!green]

  • 当前状态按结束列区分，转移只排除上一行同列。
  • 排除一个位置后的最小值，可由全局最小与第二个位置上的最小快速得到。
  • 两小值允许相等，重要的是来自不同列。
  • 第一行直接初始化，最后一行汇总所有可能终点。

易错点总结

[!yellow]

  • 将次小值理解成严格大于最小值的数，忽略不同列可以同样小。
  • 所有当前列都使用 min1，其中最小值所在列会非法连接到上一行同列。
  • 一边统计旧行最值一边覆盖旧状态，可能把当前行的累计和当作上一行前驱。
  • 只允许连接相邻三列，套用了另一道下降路径题的移动规则。
  • 将使用过的列永久禁止，错误排除隔行回到同一列的合法路径。
  • 只返回固定列的状态，终点列并未被题目限制。

相似题目

题目 难度 关联与区别
931. 下降路径最小和 中等 原题只能走到下一行相邻三列，本题可以走除同列外任意列。
265. 粉刷房子 II 困难 同样禁止相邻层选择同一列或颜色，可用上一层最小与次小值快速转移。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/37031561
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！