LeetCode 931. 下降路径最小和

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 931. 下降路径最小和

思路分析

解法一：动态规划（推荐）

核心思路：

dp[i][j] 表示到达第 i 行第 j 列的最小路径和。

由上一行的 j-1、j、j+1 转移取最小。

使用滚动数组优化空间。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示矩阵大小。

空间复杂度：O(n)。

import java.util.Arrays;

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 ans = dp[0];
        for (int v : dp) {
            ans = Math.min(ans, v);
        }
        return ans;
    }
}

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
	}

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

相似题目

题目	难度	考察点
64. 最小路径和	中等	DP
120. 三角形最小路径和	中等	DP
1289. 下降路径最小和 II	困难	DP
63. 不同路径 II	中等	DP
329. 矩阵中的最长递增路径	困难	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/86656014