6110. 网格图中递增路径的数目

Difficulty
Hard
Tags
DFS
URL
https://leetcode.cn/problems/number-of-increasing-paths-in-a-grid/
Star
给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。
请你返回在网格图中从 任意 格子出发，达到 任意 格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 109 + 7 取余 后返回。
如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。
示例 1：
notion imagenotion image
输入：grid = [[1,1],[3,4]]
输出：8
解释：严格递增路径包括：
- 长度为 1 的路径：[1]，[1]，[3]，[4] 。
- 长度为 2 的路径：[1 -> 3]，[1 -> 4]，[3 -> 4] 。
- 长度为 3 的路径：[1 -> 3 -> 4] 。
路径数目为 4 + 3 + 1 = 8 。
示例 2：
输入：grid = [[1],[2]]
输出：3
解释：严格递增路径包括：
- 长度为 1 的路径：[1]，[2] 。
- 长度为 2 的路径：[1 -> 2] 。
路径数目为 2 + 1 = 3 。
提示：
  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 105
  • 1 <= grid[i][j] <= 105

法1 记忆化搜索

思路
count[i][j]为 以grid[i][j]为起点的递增路径数量。可知，count[i][j]只与grid[i][j]上下左右的单元格有关系。
最后答案就是以每一个单元格为起点递增路径的数量。
题解
class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        # count[i][j] 记录了以grid[i][j] 为起点 的路径数量
        # 
        self.MOD = 10 ** 9 + 7
        count = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
        res = 0
        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):
                res += self.dfs(row=i, 
                                col=j, 
                                grid=grid, 
                                count=count, 
                                prev=-float("inf"))
        # print(count)
        return res % self.MOD

    def dfs(self, row, col, grid, count, prev):
        if row < 0 or row >= len(count) or col < 0 or col >= len(count[0]):
            return 0
        
        if grid[row][col] <= prev:
            return 0

        if count[row][col] != 0:
            return count[row][col]

        res = 1
        for d in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            res += self.dfs(row+d[0], col+d[1], grid, count, grid[row][col])

        count[row][col] = res % self.MOD

        return res % self.MOD