题目地址(931. 下降路径最小和)

https://leetcode-cn.com/problems/minimum-falling-path-sum/

题目描述

  1. 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
  3. 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
  7. 示例 1：
  9. 输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
  10. 输出：13
  11. 解释：下面是两条和最小的下降路径，用加粗+斜体标注：
  12. [[2,1,3],      [[2,1,3],
  13.  [6,5,4],       [6,5,4],
  14.  [7,8,9]]       [7,8,9]]
  17. 示例 2：
  19. 输入：matrix = [[-19,57],[-40,-5]]
  20. 输出：-59
  21. 解释：下面是一条和最小的下降路径，用加粗+斜体标注：
  22. [[-19,57],
  23.  [-40,-5]]
  26. 示例 3：
  28. 输入：matrix = [[-48]]
  29. 输出：-48
  34. 提示：
  36. n == matrix.length
  37. n == matrix[i].length
  38. 1 <= n <= 100
  39. -100 <= matrix[i][j] <= 100

前置知识


公司

  • 暂无

思路

这个 dp 函数的含义如下：
从第一行（matrix[0][..]）向下落，落到位置 matrix[i][j] 的最小路径和为 dp(matrix, i, j)。

对于 matrix[i][j]，只有可能从 matrix[i-1][j], matrix[i-1][j-1], matrix[i-1][j+1] 这三个位置转移过来。
那么，只要知道到达 (i-1, j), (i-1, j-1), (i-1, j+1) 这三个位置的最小路径和，加上 matrix[i][j] 的值，就能够计算出来到达位置 (i, j) 的最小路径和：
image.png

base case 为什么是 i == 0，返回值为什么是 matrix[0][j]，这是根据 dp 函数的定义所决定的。
回顾我们的 dp 函数定义：
从第一行（matrix[0][..]）向下落，落到位置 matrix[i][j] 的最小路径和为 dp(matrix, i, j)。
根据这个定义，我们就是从 matrix[0][j] 开始下落。那如果我们想落到的目的地就是 i == 0，所需的路径和当然就是 matrix[0][j] 呗。

再说说备忘录 memo 的初始值为什么是 13212，这是由题目给出的数据范围决定的。
备忘录 memo 数组的作用是什么？
就是防止重复计算，将 dp(matrix, i, j) 的计算结果存进 memo[i][j]，遇到重复计算可以直接返回。
那么，我们必须要知道 memo[i][j] 到底存储计算结果没有，对吧？如果存结果了，就直接返回；没存，就去递归计算。
所以，memo 的初始值一定得是特殊值，和合法的答案有所区分。
我们回过头看看题目给出的数据范围：

matrix 是 n x n 的二维数组，其中 1 <= n <= 100；对于二维数组中的元素，有 -100 <= matrix[i][j] <= 100。

假设 matrix 的大小是 100 x 100，所有元素都是 100，那么从第一行往下落，得到的路径和就是 100 x 100 = 10000，也就是最大的合法答案。
类似的，依然假设 matrix 的大小是 100 x 100，所有元素是 -100，那么从第一行往下落，就得到了最小的合法答案 -100 x 100 = -10000。
也就是说，这个问题的合法结果会落在区间 [-10000, 10000] 中。
所以，我们 memo 的初始值就要避开区间 [-10000, 10000]，换句话说，memo 的初始值只要在区间 (-inf, -10001] U [10001, +inf) 中就可以。

关键点


代码

  • 语言支持：Java

Java Code:

  2. class Solution {
  3.         public int minFallingPathSum(int[][] matrix) {
  4.             //返回值  取最大值
  5.             int res = Integer.MAX_VALUE;
  6.             //矩阵的行数 因为是正方形 所以一样
  7.             int n = matrix.length;
  8.             //new一个二维的dp数组
  9.             memo = new int[n][n];
  10.             //初始化dp
  11.             for (int i = 0; i <n ; i++) {
  12.                 Arrays.fill(memo[i],66666);
  13.             }
  14.             //n-1行 i是列 matrix[n-1][0]..matrix[n-1][1]..matrix[n-1][n-1]
  15.             for (int i = 0; i < n; i++) {
  16.                 //返回值从n-1这一行的几个数的dp方法的返回值中取一个最小的
  17.                 res = Math.min(res, dp(matrix, n - 1, i));
  18.             }
  19.             return res;
  20.         }
  22.         //备忘录
  23.         int[][] memo ;
  24.         public int dp(int[][] matrix, int i, int j) {
  25.             //验证角标越界
  26.             if (i >= matrix.length || j >= matrix[0].length || i < 0 || j < 0) {
  27.                 //实例范围是0-100 矩阵最大值为10000
  28.                 return 99999;
  29.             }
  30.             //base case
  31.             if (i == 0) {
  32.                 return matrix[0][j];
  33.             }
  34.             //验证备忘录 防止重复计算
  35.             if (memo[i][j] != 66666) {
  36.                 return memo[i][j];
  37.             }
  38.             //状态转移
  39.              memo[i][j] = matrix[i][j] + min(
  40.             dp(matrix, i - 1, j), 
  41.             dp(matrix, i - 1, j - 1),
  42.             dp(matrix, i - 1, j + 1)
  43.         );
  44.             return memo[i][j];
  45.         }
  46.         public int min (int a , int b ,int c){
  47.             return Math.min(a, Math.min(b, c));
  48.         }
  49.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：931. 下降路径最小和 - 图2#card=math&code=O%28n%29&id=TJ7IK)
  • 空间复杂度：931. 下降路径最小和 - 图3#card=math&code=O%28n%29&id=EkVdr)