leetcode：329. The longest incremental path in the matrix [DFS + cache + no backtracking + elegance]

analysis

Why not visit, Because it is a strictly increasing sequence , So there must be no turning back , So there's no need to visit
Then the idea is the same , Traverse each starting point
dfs The maximum length is returned , The recorded parameters include the current location , And the position of the previous number
Because what we traverse is the starting point , So natural , The position of the previous number is the selected starting point
Then because if we fix the current position , And the size of the previous number , The maximum distance you can walk is also fixed
So it can be memorized
The core code here is , Leave the current problem to the next step （ Next, meet the conditions ）
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 grace 
        #  When the point is fixed with the previous point , The maximum length it can walk is fixed 
        @cache
        def dfs(r, c, pre):
            
            res = 1 #  At least at this point 
            
            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
        #  Traverse each starting point to get the maximum value of different starting points 
        for i in range(m):
            for j in range(n):
                ans = max(ans, dfs(i, j, matrix[i][j]))
                    
        
        return ans

summary

Find the best path in two-dimensional graph
You can consider dfs + cache
dfs What is recorded , What are the parameters , What is the output
When can I enter the next dfs
the previous dfs And the next dfs What does it matter
need visit Prevent repetition
Need backtracking ...