leetcode：329. 矩阵中的最长递增路径【dfs + cache + 无需回溯 + 优雅】

分析

为什么不用visit，因为是严格递增序列，所以一定不存在还能回头走的情况，所以无需visit
然后思路也是一样，遍历每个起点
dfs返回的是最大长度，记录的参数包括当前的位置，以及前一个数的位置
由于我们遍历的是起点，所以天然的，前一个数的位置就是所选的起点
然后由于如果我们固定了当前的位置，以及前一个数的大小，这个能走的最大距离也是固定的
因此可以记忆化
这里面的核心代码就是，把现在的难题丢给下一步（下一步满足条件）
res = max(res, dfs(nr, nc, matrix[nr][nc]) + 1)

ac code

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])     
        maxn = 0

        # dfs + memory优雅
        # 当点和上一个点固定，它能走的最大长度也就固定
        @cache
        def dfs(r, c, pre):
            
            res = 1 # 最少也是当前这个点
            
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > pre:

                    res = max(res, dfs(nr, nc, matrix[nr][nc]) + 1)
            return res
        

        ans = 0
        # 遍历每个起点获得不同起点的最大值
        for i in range(m):
            for j in range(n):
                ans = max(ans, dfs(i, j, matrix[i][j]))
                    
        
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

总结

二维图求最什么的路径啥的
可以考虑dfs + cache
dfs记录的是啥，参数是啥，输出是啥
什么时候能进入下一个dfs
上一个dfs和下一个dfs有什么关系
需要visit防止重复吗
需要回溯吗。。。