题解 | #矩阵最长递增路径#

矩阵最长递增路径，dfs+动态规划

心路历程：看一眼题，求最长路径，欧，简单，就是从一个起点开始，用dfs把每条能走的道都走一遍，最后看所有的路中谁最长，类似于求树的深度嘛。根据这样的想法写完代码，什么，居然没有过。再瞄了一眼题，欧，原来起点不固定，那加个循环，把矩阵中所有点都遍历一边，这样总能找到最大值了吧，就像岛屿问题，写完提交，什么，居然超时了。欧，也是，里面涉及好多重复运算。怎么减少重复运算呢，咦，如果算一次记录点东西，就可以避免重复计算了撒。但是记录什么呢，欧，有了，每到一个点(i,j)，就记录以该点为起点的最长递增路径长。提交，什么，还是超时。突然想到，dfs的时候就已经遍历了很多点了，以这些点为起点的最长递增路径长如果能直接算，岂不就省事多了。思考......，直接以没有路的那个点为1，往上依次递增就可以得到以点(i,j)为起点的一条路的长度了，在所有路中选最长那条，以点(i,j)为起点的最长路径。突然有个疑问，dfs时求的以点(i,j)为起点的最长路径，与遍历的时候求的以点(i,j)为起点的最长路径是不是一样的呢，当然是啦，都是同一个点嘛。

class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        dirs = [
            lambda x, y: (x-1, y), lambda x, y: (x, y+1),
            lambda x, y: (x+1, y), lambda x, y: (x, y-1),
        ]
        m, n = len(matrix), len(matrix[0])
        # 状态数组，dp[i][j]表示以（i,j）为起点的最长递增序列长度
        dp = [[0 for _ in range(n)] for _ in range(m)] 
        def dfs(x, y):
            count = 0
            for dir_ in dirs:
                new_x, new_y = dir_(x,y)
                if 0<=new_x<m and 0<=new_y<n and matrix[x][y] < matrix[new_x][new_y]:
                    if dp[new_x][new_y]:   # 状态已经存在，直接使用
                        dp[x][y]= max(dp[x][y], dp[new_x][new_y]+1)
                    else:
                        dp[x][y]= max(dp[x][y], dfs(new_x, new_y)+1)
                    count += 1
            if not count:                  # 该值比周围值都大，即为递增尾部，长度为1
                dp[x][y] = 1
            return dp[x][y]                # 返回前一个位置的最大递增长度
        # 循环，逐一计算dp[i][j]
        max_len = 0                        # 非全局，需要维护一个最大值
        for i in range(m):
            for j in range(n):
                if dp[i][j] == 0:
                    dfs(i,j)
                max_len = max(max_len, dp[i][j])
        return max_len