LeetCode 1289. 下降路径最小和 II

Categories:

题目描述
思路分析
1. 解法一：DP + 维护两小值（推荐）
相似题目

题目描述

✅ 1289. 下降路径最小和 II

思路分析

解法一：DP + 维护两小值（推荐）

核心思路：

设 dp[j] 为当前行选择列 j 的最小路径和。

对上一行找出最小值 min1 与次小值 min2 及其列索引。

若当前列与最小值列相同，则用 min2，否则用 min1 进行转移。

复杂度分析：

时间复杂度：O(n^2)，n 为矩阵边长。

空间复杂度：O(n)，滚动数组。

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 idx1 = -1;
            for (int j = 0; j < n; j++) {
                int v = dp[j];
                if (v < min1) {
                    min2 = min1;
                    min1 = v;
                    idx1 = j;
                } else if (v < min2) {
                    min2 = v;
                }
            }

            int[] ndp = new int[n];
            for (int j = 0; j < n; j++) {
                int add = (j == idx1) ? min2 : min1;
                ndp[j] = grid[i][j] + add;
            }
            dp = ndp;
        }

        int ans = dp[0];
        for (int v : dp) {
            ans = Math.min(ans, v);
        }
        return ans;
    }
}

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)
        idx1 := -1
        for j := 0; j < n; j++ {
            v := dp[j]
            if v < min1 {
                min2 = min1
                min1 = v
                idx1 = j
            } else if v < min2 {
                min2 = v
            }
        }

        ndp := make([]int, n)
        for j := 0; j < n; j++ {
            add := min1
            if j == idx1 {
                add = min2
            }
            ndp[j] = grid[i][j] + add
        }
        dp = ndp
    }

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

相似题目

题目	难度	考察点
931. 下降路径最小和	中等	DP
64. 最小路径和	中等	DP
120. 三角形最小路径和	中等	DP
221. 最大正方形	中等	DP
62. 不同路径	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/37031561