leetcode：6110. The number of incremental paths in the grid graph [DFS + cache]

analysis

dfs Memory search , Record the position of the current point （ At least one path ）, Then throw the problem to the next accessible point , add dfs
Search each location as the starting point , The total number of incremental paths that can be formed later
Traverse different starting points , From this, we get the total number of paths

ac code

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        m, n = len(grid), len(grid[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 grid[nr][nc] > pre:

                    res += dfs(nr, nc, grid[nr][nc])
            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 += dfs(i, j, grid[i][j])
                ans %= MOD
                
                    
        
        return ans

summary

The number of classic two-dimensional incremental paths is counted
Similar topics have the longest incremental path , Only need to res += Change to res = max(…) that will do