931. 下降路径最小和

难度: 中等

来源: 每日一题 2023.07.13

---

给你一个 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].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100

class Solution {
    public int minFallingPathSum(int[][] matrix) {

    }
}

分析与题解

---

• 动态规划

  这个题白天的是我想的就是贪心算法,利用动态规划来做,动态规划我们就需要找到状态转移方程, 我们知道能到达 dp[i][j] 的最多只有如下的三个位置.

  

  我们只需要找到这三个值中最少的数值,加上 dp[i][j] 即为 [i][j] 位置的最少路径, 然后我们只需要找到最后一行中的最少路径值即可. 我们主要分为以下几部.

  • 如果在第一行时 ( i = 0 ), 作为状态转移方程的初始状态.

  • 如果在其他行, 最多需要判断 matrix[i - 1][j - 1] matrix[i - 1][j]
matrix[i - 1][j + 1] 三者的其中的最少值.

  • 在最后一行时, 需要找到路径的最少值,即可完成整个题解.

  最终,整个解题过程如下所示.

  class Solution {
      public int minFallingPathSum(int[][] matrix) {
          int rowLength = matrix[0].length;
          int [][] dp = new int[matrix.length][rowLength];
  
          int resultValue = Integer.MAX_VALUE;
  
          for (int i = 0; i < matrix.length; i++) {
              for(int j = 0; j < rowLength ; j++) {
                  if (i == 0) {
                      // 处理第一行起始数据
                      dp[0][j] = matrix[0][j];
                  } else {
                      // 处理三个数
                      int minValue = Integer.MAX_VALUE;
                      minValue = Math.min(minValue, dp[i - 1][j]);
                      if ( j - 1 >= 0 ) {
                          minValue = Math.min(minValue, dp[i - 1][j - 1]);
                      } 
                      if ( j + 1 <= rowLength -1) {
                          minValue = Math.min(minValue, dp[i - 1][j + 1]);
                      } 
                      dp[i][j] = minValue + matrix[i][j];
                  }
                  // 找到最后一行的最少值
                  if (i == matrix.length - 1) {
                      resultValue = Math.min(resultValue, dp[i][j]);
                  }
              }
          }
          return resultValue;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n²)
  • 空间复杂度: O(n²)

  结果如下所示.