题目分析

最长递增路径问题，是一个有向图问题，而且要更为复杂一些，不是一个简单的单向图，而是多向图。要想找到最长的一条路径，必然要使用两种常见的搜索方法，DFS和BFS。但是这两个搜索方法都有一个特点，就是已知起始点然后进行搜索，如果不知道起始点，如何搜索得到最长路径呢？一个最暴力的方法是遍历所有起始点，从每一个点开始搜索，并且比较哪一个最长。这样的方法时间复杂度太高，浪费的太多的计算资源，必然无法通过所有的样例，那么如何保存计算过程中的计算结果呢？有一个专业术语称为记忆化，下面给小伙伴聊一聊记忆化的DFS。

记忆化+DFS

Python常用库给我们提供了一种重要的装饰器，lru_cache，其位于functools包下。主要是用于函数的递归调用时，会记录递归调用的结果，这样下次遇到同样的参数时，可以直接调出，不需要再次递归调用。其本质是一个字典，键是参数值，值是递归调用的结果。例如使用递归求斐波那契数列时，计算f(5)会使用到f(3)+f(4)，如果不使用lru_cache装饰器，已经得到了f(3)时，递归调用f(4)时还会重新调用f(3)的，这样就会出现指数爆炸式的计算量增长。当计算f(100)时，会递归调用f(99)和f(98)，如果有了lru_cache，就可以从字典中直接取出99和98对应的值，此时的时间复杂度为线性的，而递归是指数级的。
这道题也类似，我们遍历所有的点，从第一个点A去寻找最长递增路径的长度，如果寻找到了某一个点B，那么会记录从点B出发的最长递增路径，那么下次当其他点也寻找到了这个点B时，就不用重新遍历点B。时间复杂度为$O(mn)$，空间复杂度为$O(mn)$，m和n为矩阵的行和列。

from functools import lru_cache


class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if not matrix:
            return 0
        direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        m, n = len(matrix), len(matrix[0])

        @lru_cache(None)
        def dfs(i, j):
            res = 1
            for x, y in direction:
                new_x, new_y = i + x, j + y
                if 0 <= new_x < m and 0 <= new_y < n and matrix[i][j] > matrix[new_x][new_y]:
                    res = max(res, dfs(new_x, new_y) + 1)
            return res

        result = 0
        for i in range(m):
            for j in range(n):
                result = max(result, dfs(i, j))
        return result

多源BFS

这道题目也可以使用多源BFS来求解，我们理解题意可以发现，路径的终点一定是无法向四周扩展的点，也就是说终点的值一定大于周围的值，玩过围棋的小伙伴们更加了解这个说法，可以说是气，说明这个棋子还有几口气，如果周围都是对方的子，说明这个子没有气了，这也是同样道理，因此我们可以遍历所有的点，对每一个点计算四个方向的值，计算每一个点的气。然后对于每一个气为0的点，作为源，然后进行BFS广度优先搜索，搜索出距离源点为1且满足小于当前值的点，并且更新这些点的气，气的值减1，如果气为0，则加入下一轮的寻找过程中(这一步是关键，为什么气为0则加入下一轮，是因为如果气不为0，说明还有其他点可以到达，说明现在就到达这个点的路径必然不是最长路径)，依次寻找距离为2的点……，直到所有点都寻找完毕，此时的距离就是最长的路径。
这个算法的**时间复杂度为$O(mn)$，空间复杂度也是$O(mn)$**，我就直接将官方的题解借鉴过来，供大家参考。

class Solution:
    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def longestIncreasingPath(self, matrix):
        if not matrix:
            return 0

        rows, columns = len(matrix), len(matrix[0])
        outdegrees = [[0] * columns for _ in range(rows)]
        queue = collections.deque()
        for i in range(rows):
            for j in range(columns):
                for dx, dy in Solution.DIRS:
                    newRow, newColumn = i + dx, j + dy
                    if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] > matrix[i][j]:
                        outdegrees[i][j] += 1
                if outdegrees[i][j] == 0:
                    queue.append((i, j))

        ans = 0
        while queue:
            ans += 1
            size = len(queue)
            for _ in range(size):
                row, column = queue.popleft()
                for dx, dy in Solution.DIRS:
                    newRow, newColumn = row + dx, column + dy
                    if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] < matrix[row][column]:
                        outdegrees[newRow][newColumn] -= 1
                        if outdegrees[newRow][newColumn] == 0:
                            queue.append((newRow, newColumn))

        return ans

刷题总结

多次强调，DFS和BFS问题是高频考点，现在的题目难度越来越高，因此在掌握了基本的DFS和BFS之后，还需要多刷题，掌握一些奇技淫巧，这样遇到图相关的问题才能从容应对。