下降路径最小和
难度:
标签:
题目描述
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
示例 1：
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]] 输出：13 解释：如图所示，为和最小的两条下降路径
示例 2：
输入：matrix = [[-19,57],[-40,-5]] 输出：-59 解释：如图所示，为和最小的下降路径
提示：
n == matrix.length == matrix[i].length1 <= n <= 100-100 <= matrix[i][j] <= 100
代码结果
运行时间: 37 ms, 内存: 16.9 MB
/*
* The problem is to find the minimum sum of a falling path through a given n x n integer matrix.
* We can use Java Streams to simplify the operations for finding the minimum path sum.
* We will still use dynamic programming but will utilize streams to compute the minimum values.
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
int minAbove = matrix[i-1][j];
if (j > 0) {
minAbove = Math.min(minAbove, matrix[i-1][j-1]);
}
if (j < n - 1) {
minAbove = Math.min(minAbove, matrix[i-1][j+1]);
}
matrix[i][j] += minAbove;
}
}
return Arrays.stream(matrix[n-1]).min().getAsInt();
}
}解释
方法:
这个解题思路采用动态规划方法。它在原矩阵上进行修改，通过逐行更新来得到最小的下降路径和。具体地，对于矩阵中的每个元素，它将当前元素值更新为自身加上其正上方，左上方和右上方三个可能的前驱元素中的最小值。对于每行的第一个和最后一个元素，因为不存在左上或右上元素，所以只考虑可行的前驱元素。整个过程重复直到矩阵的最后一行，然后返回最后一行中的最小值作为结果。
时间复杂度:
O(n^2)
空间复杂度:
O(1)
代码细节讲解
🦆
在动态规划解法中，对于矩阵的边界处理（如第一列和最后一列），是否有其他可能的优化方法来减少条件判断？
▷🦆
该算法是否能够处理所有的 n x n 矩阵，包括 n=1 的情况？如果矩阵仅有一行或一列，算法的行为是如何的？
▷🦆
在返回最后一行中的最小值时，是否考虑了所有可能的路径，包括那些可能的斜向下降路径？
▷🦆
如果矩阵中包含负数，此算法是否依然有效？会不会影响到最终的下降路径最小和的计算？
▷