动态规划

矩阵

  • 下降路径最小和

    难度：中等

    给你一个 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

  • 方法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution(object):
      def minFallingPathSum(self, matrix):
          """
          :type matrix: List[List[int]]
          :rtype: int
          """
          m=len(matrix)
          n=len(matrix[0])
          dp=[[0]*n for i in range(m)]
          dp[0]=matrix[0]
          for i in range(1,m):
              for j in range(0,n):
                  if j==0:
                      dp[i][j]=min(dp[i-1][j],dp[i-1][j+1])+matrix[i][j]
                  elif j==n-1:
                      dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+matrix[i][j]
                  else:
                      dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+matrix[i][j]
          return min(dp[-1])

    解析
    题目需要求出矩阵的和最小下降路径，可以求出末行每个元素的和最小下降路径，然后找到其中和最小的那一条路径即可。而根据题意，每个坐标仅可以通过它的上一排紧邻的三个坐标到达（左上，正上，右上），根据贪心思想，每个坐标的和最小下降路径长度即为它的上一排紧邻的三个坐标的和最小下降路径长度的最小值，再加上当前坐标的和。用 dp 表示和最小下降路径长度的话，即为 dp[i][j]=matrix[i][j]+min(dp[i−1][j−1],dp[i−1][j],dp[i−1][j+1])，第一列和最后一列有边界情况，需要特殊处理。而第一行每个元素的和最小下降路径长度为它们本身的值。最后返回最后一行的和最小下降路径长度的最小值即可。

复杂度分析
时间复杂度：O(n^2)，需要计算每个坐标的和最小下降路径。
空间复杂度：O(n^2)，需要记录每个坐标的和最小下降路径。因为每个坐标的和最小下降路径仅与上一行有关，因此可以使用滚动数组，使得空间复杂度降低为 O(n)。