931. 下降路径最小和

给你一个 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 解释：1+5+7=13 1+4+8=13

题解1

我们用 dp(r, c) 表示从任意位置下降到 (r, c) 路径最小和。根据题目的要求，位置(r-1, c-1)，(r-1, c) 和 (r-1, c+1) 三个位置都可以下降到 (r, c) ，因此状态转移方程为：dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+A[i][j]

• 状态：dp(r, c) 表示从任意位置下降到 (r, c) 路径最小和
• 边界条件：第一行的任意位置 dp[0][j]=A[0][j]
• 状态转移方程：dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+A[i][j]

$$ dp[i][j]=\begin{cases} min(dp[i-1,j],dp[i-1,j+1])+Ai][j] & \text{ if 矩阵的左边界 } \\ min(dp[i-1,j-1],dp[i-1,j])+A[i][j] & \text{ elif 矩阵的右边界 } \\ min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+A[i][j] & \text{ else 其他} \end{cases} $$

自顶向下

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        row, col=len(matrix), len(matrix[0])  # 矩阵列的行和列
        dic=[[None]*col for _ in range(row)]
        # 边界条件
        for i in range(col):
            dic[0][i]=matrix[0][i]

        def dp(i,j):
            if dic[i][j] != None:
                return dic[i][j]
        
        # 状态转移方程
            if j-1<0:
                dic[i][j]=min(dp(i-1,j),dp(i-1,j+1))+matrix[i][j]
            elif j+1>col-1:
                dic[i][j]=min(dp(i-1,j-1),dp(i-1,j))+matrix[i][j]
            else:
                dic[i][j]=min(dp(i-1,j-1),dp(i-1,j),dp(i-1,j+1))+matrix[i][j]
            return dic[i][j]
    
        # 最后一行，每一列
        for i in range(col):
            dp(row-1,i)
    
        return min(dic[row-1])

自底向上

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        row, col=len(matrix), len(matrix[0])  # 矩阵列的行和列

        dp=[[0]*col for _ in range(row)]
        # 边界条件
        for i in range(col):
            dp[0][i]=matrix[0][i]

        # 状态转移方程
        for i in range(1,row):
            for j in range(col):
                if j-1<0:
                    dp[i][j]=min(dp[i-1][j],dp[i-1][j+1])+matrix[i][j]
                elif j+1>col-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[row-1])

自底向上-状态压缩

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        row, col=len(matrix), len(matrix[0])  # 矩阵列的行和列

        dp=[[0]*col for _ in range(2)]
        # 边界条件
        for i in range(col):
            dp[0][i]=matrix[0][i]

        # 状态转移方程
        for i in range(1,row):
            for j in range(col):
                if j-1<0:
                    dp[i%2][j]=min(dp[(i-1)%2][j],dp[(i-1)%2][j+1])+matrix[i][j]
                elif j+1>col-1:
                    dp[i%2][j]=min(dp[(i-1)%2][j-1],dp[(i-1)%2][j])+matrix[i][j]
                else:
                    dp[i%2][j]=min(dp[(i-1)%2][j-1],dp[(i-1)%2][j],dp[(i-1)%2][j+1])+matrix[i][j]
  
        return min(dp[(row-1)%2])

329. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1：输入：matrix = [[9,9,4],[6,6,8],[2,1,1]] 输出：4 解释：最长递增路径为 [1, 2, 6, 9]。

题解1