题目

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

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

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

示例 1：
image.png

  1. 输入：grid = [[1,1],[3,4]]
  2. 输出：8
  3. 解释：严格递增路径包括：
  4. - 长度为 1 的路径：[1]，[1]，[3]，[4] 。
  5. - 长度为 2 的路径：[1 -> 3]，[1 -> 4]，[3 -> 4] 。
  6. - 长度为 3 的路径：[1 -> 3 -> 4] 。
  7. 路径数目为 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 <= 10^5

  • 1 <= grid[i][j] <= 10^5

    解题方法

    DFS + 哈希表

    设定哈希表chart[i][j]表示从第(i, j)个方格为起点能够形成的严格递增路径数目。通过 DFS 的方式搜索每个格子为起点的严格递增路径，并更新哈希表。
    时间复杂度O(mn)，空间复杂度O(mn)。
    C++代码： ```cpp class Solution { private: int m, n; int mod = 1E9+7;

    int dfs(vector>& grid, vector>& hash, int x, int y) {

      // cout<<x<<" "<<y<<endl;
  if(hash[x][y])   return hash[x][y];
  int result = 1;
  if(x>0 && grid[x-1][y]>grid[x][y])  result = (result + dfs(grid, hash, x-1, y)) % mod;
  if(y>0 && grid[x][y-1]>grid[x][y])  result = (result + dfs(grid, hash, x, y-1)) % mod;
  if(x<m-1 && grid[x+1][y]>grid[x][y])  result = (result + dfs(grid, hash, x+1, y)) % mod;
  if(y<n-1 && grid[x][y+1]>grid[x][y])  result = (result + dfs(grid, hash, x, y+1)) % mod;
  hash[x][y] = result;
  return result;

    }

public: int countPaths(vector>& grid) { m = grid.size(); n = grid[0].size(); vector> hash(m, vector(n, 0)); int sum = 0; for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { sum = (sum + dfs(grid, hash, i, j)) % mod; } } return sum; } }; ```