题目描述
给你一个 m x n
的整数网格图 grid
,你可以从一个格子移动到 4
个方向相邻的任意一个格子。
请你返回在网格图中从 任意 格子出发,达到 任意 格子,且路径中的数字是 严格递增 的路径数目。由于答案可能会很大,请将结果对 10^9 + 7
取余 后返回。
如果两条路径中访问过的格子不是完全相同的,那么它们视为两条不同的路径。
样例
输入: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。
输入: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 <= 10^5
1 <= grid[i][j] <= 10^5
算法
(记忆化搜索) $O(mn)$
- 设状态 $f(x, y)$ 表示以 $(x, y)$ 为终点的路径个数。由于拓扑关系比较复杂,所以需要通过记忆化搜索的方式遍历状态。
- 初始时,所有点都可以直接作为终点,故 $f(x, y) = 1$。
- 转移时,对于 $(x, y)$,枚举其四个方向,如果存在合法的前驱方向 $(tx, ty)$(不越界且满足 $grid(x, y) > grid(tx, ty)$),递归处理 $(tx, ty)$ 后,转移 $f(x, y) = f(x, y) + f(tx, ty)$。
- 最终答案为 $\sum f(x, y)$。
时间复杂度
- 状态数共 $O(mn)$,转移时间为常数,故总时间复杂度为 $O(mn)$。
空间复杂度
- 需要 $O(mn)$ 的额外空间存储状态数和递归调用的系统栈。
C++ 代码
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int mod = 1000000007;
class Solution {
private:
int m, n;
vector<vector<int>> f;
int solve(int x, int y, const vector<vector<int>> &grid) {
if (f[x][y] != -1)
return f[x][y];
int r = 1;
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx < 0 || tx >= m || ty < 0 || ty >= n)
continue;
if (grid[tx][ty] >= grid[x][y])
continue;
r = (r + solve(tx, ty, grid)) % mod;
}
return f[x][y] = r;
}
public:
int countPaths(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
f.resize(m, vector<int>(n, -1));
int ans = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
ans = (ans + solve(i, j, grid)) % mod;
return ans;
}
};