526互联

[LeetCode] 931. Minimum Falling Path Sum

发布时间 2023-07-13 08:05:58作者: CNoodle

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Example 1:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.

Example 2:

Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 100
  • -100 <= matrix[i][j] <= 100

下降路径最小和。

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-falling-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是动态规划。这里我提供一个 DFS + 备忘录的做法，属于dp里自上而下那种类型。思路直接参见代码注释，如果不明白，需要先做比如 unique path 那一类的矩阵类的动态规划的基础题。注意这道题的 base case 是如果矩阵只有一行，那么下降路径的最小值就是每个 col 上的那个值。

时间O(n^2)

空间O(n^2)

Java实现

 1 class Solution {
 2     int n;
 3     int[][] memo;
 4 
 5     public int minFallingPathSum(int[][] matrix) {
 6         n = matrix.length;
 7         int res = Integer.MAX_VALUE;
 8         memo = new int[n][n];
 9         for (int[] row : memo) {
10             Arrays.fill(row, Integer.MAX_VALUE);
11         }
12 
13         for (int j = 0; j < n; j++) {
14             res = Math.min(res, dp(matrix, n - 1, j));
15         }
16         return res;
17     }
18 
19     private int dp(int[][] matrix, int i, int j) {
20         // corner case
21         if (i < 0 || j < 0 || i >= n || j >= n) {
22             return Integer.MAX_VALUE;
23         }
24 
25         // base case
26         if (i == 0) {
27             return matrix[0][j];
28         }
29 
30         // normal case
31         if (memo[i][j] != Integer.MAX_VALUE) {
32             return memo[i][j];
33         }
34 
35         memo[i][j] = matrix[i][j] + min(
36             dp(matrix, i - 1, j),
37             dp(matrix, i - 1, j - 1),
38             dp(matrix, i - 1, j + 1)
39         );
40         return memo[i][j];
41     }
42 
43     private int min(int a, int b, int c) {
44         return Math.min(a, Math.min(b, c));
45     }
46 }
47 
48 // dp自上而下 + memo

 

LeetCode 题目总结