---
comments: true
difficulty: 困难
edit_url: https://github.com/doocs/leetcode/edit/main/solution/2300-2399/2328.Number%20of%20Increasing%20Paths%20in%20a%20Grid/README.md
rating: 2001
source: 第 300 场周赛 Q4
tags:
- 深度优先搜索
- 广度优先搜索
- 图
- 拓扑排序
- 记忆化搜索
- 数组
- 动态规划
- 矩阵
---
# [2328. 网格图中递增路径的数目](https://leetcode.cn/problems/number-of-increasing-paths-in-a-grid)
[English Version](/solution/2300-2399/2328.Number%20of%20Increasing%20Paths%20in%20a%20Grid/README_EN.md)
## 题目描述
给你一个 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.lengthn == grid[i].length1 <= m, n <= 10001 <= m * n <= 1051 <= grid[i][j] <= 105
## 解法
### 方法一：记忆化搜索
我们设计一个函数 $dfs(i, j)$，表示从网格图中的第 $i$ 行第 $j$ 列的格子出发，能够到达任意格子的严格递增路径数目。那么答案就是 $\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} dfs(i, j)$。搜索过程中，我们可以用一个二维数组 $f$ 记录已经计算过的结果，避免重复计算。
函数 $dfs(i, j)$ 的计算过程如下：
- 如果 $f[i][j]$ 不为 $0$，说明已经计算过，直接返回 $f[i][j]$；
- 否则，我们初始化 $f[i][j] = 1$，然后枚举 $(i, j)$ 的四个方向，如果某个方向的格子 $(x, y)$ 满足 $0 \leq x \lt m$, $0 \leq y \lt n$ 且 $grid[i][j] \lt grid[x][y]$，我们就可以从格子 $(i, j)$ 出发，到达格子 $(x, y)$，且路径上的数字是严格递增的，因此有 $f[i][j] += dfs(x, y)$。
最后，我们返回 $f[i][j]$。
答案为 $\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} dfs(i, j)$。
时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是网格图的行数和列数。
相似题目：
- [329. 矩阵中的最长递增路径](https://github.com/doocs/leetcode/blob/main/solution/0300-0399/0329.Longest%20Increasing%20Path%20in%20a%20Matrix/README.md)。
#### Python3
```python
class Solution:
def countPaths(self, grid: List[List[int]]) -> int:
@cache
def dfs(i: int, j: int) -> int:
ans = 1
for a, b in pairwise((-1, 0, 1, 0, -1)):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[i][j] < grid[x][y]:
ans = (ans + dfs(x, y)) % mod
return ans
mod = 10**9 + 7
m, n = len(grid), len(grid[0])
return sum(dfs(i, j) for i in range(m) for j in range(n)) % mod
```
#### Java
```java
class Solution {
private int[][] f;
private int[][] grid;
private int m;
private int n;
private final int mod = (int) 1e9 + 7;
public int countPaths(int[][] grid) {
m = grid.length;
n = grid[0].length;
this.grid = grid;
f = new int[m][n];
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;
}
private int dfs(int i, int j) {
if (f[i][j] != 0) {
return f[i][j];
}
int ans = 1;
int[] dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y]) {
ans = (ans + dfs(x, y)) % mod;
}
}
return f[i][j] = ans;
}
}
```
#### C++
```cpp
class Solution {
public:
int countPaths(vector>& grid) {
const int mod = 1e9 + 7;
int m = grid.size(), n = grid[0].size();
int f[m][n];
memset(f, 0, sizeof(f));
function dfs = [&](int i, int j) -> int {
if (f[i][j]) {
return f[i][j];
}
int ans = 1;
int dirs[5] = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y]) {
ans = (ans + dfs(x, y)) % mod;
}
}
return f[i][j] = ans;
};
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;
}
};
```
#### Go
```go
func countPaths(grid [][]int) (ans int) {
const mod = 1e9 + 7
m, n := len(grid), len(grid[0])
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
var dfs func(int, int) int
dfs = func(i, j int) int {
if f[i][j] != 0 {
return f[i][j]
}
f[i][j] = 1
dirs := [5]int{-1, 0, 1, 0, -1}
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y] {
f[i][j] = (f[i][j] + dfs(x, y)) % mod
}
}
return f[i][j]
}
for i, row := range grid {
for j := range row {
ans = (ans + dfs(i, j)) % mod
}
}
return
}
```
#### TypeScript
```ts
function countPaths(grid: number[][]): number {
const mod = 1e9 + 7;
const m = grid.length;
const n = grid[0].length;
const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
const dfs = (i: number, j: number): number => {
if (f[i][j]) {
return f[i][j];
}
let ans = 1;
const dirs: number[] = [-1, 0, 1, 0, -1];
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y]) {
ans = (ans + dfs(x, y)) % mod;
}
}
return (f[i][j] = ans);
};
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
ans = (ans + dfs(i, j)) % mod;
}
}
return ans;
}
```