leetcode：6110. 网格图中递增路径的数目【dfs + cache】

分析

dfs记忆化搜索，记录当前点的位置（至少有一条路径），然后把问题扔给下一个能走到的点，加上dfs
搜索每个位置为起点，后面能组成递增路径的总个数
遍历不同起点，由此得到总路径数

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优雅
        # 当点和上一个点固定，它能走的最大长度也就固定
        @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 grid[nr][nc] > pre:

                    res += dfs(nr, nc, grid[nr][nc])
            return res
        

        ans = 0
        # 遍历每个起点获得不同起点的最大值
        for i in range(m):
            for j in range(n):
                ans += dfs(i, j, grid[i][j])
                ans %= MOD
                
                    
        
        return ans

总结

经典二维递增路径数量统计了
类似题目有最长的递增路径，只需要把res += 改成res = max(…)即可