2328-网格图中递增路径的数目

给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。

请你返回在网格图中从 任意 格子出发，达到 任意 格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对
109 + 7 取余 后返回。

如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。

示例 1：

**输入：** 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

本题 视频讲解 已出炉，包含本题可以使用记忆化搜索的原理，欢迎点赞三连~

---

根据题意，我们可以遍历每个格子，以这个格子为起点，往上下左右四个方向前进，如果下一个格子的值比当前格子的值大，则可以前进。

定义 f[i][j] 表示以第 i 行第 j 列的格子为起点的路径数。

由于路径中的数字严格递增，状态无后效性，可以用动态规划解决。

我们把四个方向可以走的格子所对应的状态 f[i’][j’] 累加起来，再加上 1，即当前格子组成的长度为 1 的路径，即为 f[i][j]。

代码实现时可以用记忆化搜索。

复杂度分析

• 时间复杂度：O(mn)。有 O(mn) 个状态，每个状态有 O(1) 个转移来源，计算所有状态的时间为 O(mn)。
• 空间复杂度：O(mn)。

相似题目

• 329. 矩阵中的最长递增路径

[sol1-Python3]

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        m, n = len(grid), len(grid[0])
        @cache
        def dfs(i: int, j: int) -> int:
            res = 1
            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):
                if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j]:
                    res += dfs(x, y)
            return res % MOD
        return sum(dfs(i, j) for i in range(m) for j in range(n)) % MOD

[sol1-Java]

class Solution {
    static final int MOD = (int) 1e9 + 7;
    static final int[][] dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    int m, n;
    int[][] grid, f;

    public int countPaths(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        f = new int[m][n];
        for (int i = 0; i < m; i++) Arrays.fill(f[i], -1);
        var ans = 0;
        for (var i = 0; i < m; ++i)
            for (var j = 0; j < n; ++j)
                ans = (ans + dfs(i, j)) % MOD;
        return ans;
    }

    int dfs(int i, int j) {
        if (f[i][j] != -1) return f[i][j];
        var res = 1;
        for (var d : dirs) {
            int x = i + d[0], y = j + d[1];
            if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] > grid[i][j])
                res = (res + (dfs(x, y))) % MOD;
        }
        return f[i][j] = res;
    }
}

[sol1-C++]

class Solution {
    const int MOD = 1e9 + 7;
    const int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
public:
    int countPaths(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size();
        int f[m][n]; memset(f, -1, sizeof(f));
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (f[i][j] != -1) return f[i][j];
            int res = 1;
            for (auto &d : dirs) {
                int x = i + d[0], y = j + d[1];
                if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] > grid[i][j])
                    res = (res + (dfs(x, y))) % MOD;
            }
            return f[i][j] = res;
        };
        int ans = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                ans = (ans + dfs(i, j)) % MOD;
        return ans;
    }
};

[sol1-Go]

var dirs = []struct{ x, y int }{ {-1, 0}, {1, 0}, {0, -1}, {0, 1} }

func countPaths(grid [][]int) (ans int) {
	const mod int = 1e9 + 7
	m, n := len(grid), len(grid[0])
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(int, int) int
	dfs = func(i, j int) int {
		if f[i][j] != -1 {
			return f[i][j]
		}
		res := 1
		for _, d := range dirs {
			if x, y := i+d.x, j+d.y; 0 <= x && x < m && 0 <= y && y < n && grid[x][y] > grid[i][j] {
				res = (res + dfs(x, y)) % mod
			}
		}
		f[i][j] = res
		return res
	}
	for i, row := range grid {
		for j := range row {
			ans = (ans + dfs(i, j)) % mod
		}
	}
	return
}