网格图中递增路径的数目
难度:
标签:
题目描述
给你一个 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
代码结果
运行时间: 642 ms, 内存: 31.7 MB
/*
* 思路：
* 1. 使用动态规划来记录从每个格子出发的严格递增路径数量。
* 2. 按照格子内的值从小到大遍历所有格子，并更新相邻格子的路径数量。
* 3. 使用Java Stream API进行格子排序和遍历。
* 4. 使用模数运算（10^9 + 7）来防止结果溢出。
*/
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
private static final int MOD = 1000000007;
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int countPaths(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
List<int[]> cells = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cells.add(new int[]{i, j});
}
}
cells = cells.stream().sorted(Comparator.comparingInt(a -> grid[a[0]][a[1]])).collect(Collectors.toList());
long result = 0;
for (int[] cell : cells) {
int i = cell[0];
int j = cell[1];
dp[i][j] = 1;
for (int[] dir : DIRS) {
int x = i + dir[0];
int y = j + dir[1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > grid[i][j]) {
dp[i][j] = (dp[i][j] + dp[x][y]) % MOD;
}
}
result = (result + dp[i][j]) % MOD;
}
return (int) result;
}
}解释
方法:
该题解采用了深度优先搜索（DFS）与记忆化的方法来解决问题。首先定义一个memo数组来存储每个格子出发的递增路径数量，避免重复计算。对于网格中的每个单元格，使用DFS探索所有可能的递增路径。通过递归调用，每次尝试向四个方向扩展路径，只有当新的单元格值大于当前单元格值时，才会继续递归搜索。每个单元格的递增路径数量是它自身（长度为1的路径）加上从它可以到达的四个方向上其他单元格的递增路径数量之和。最后，将所有单元格的路径数加起来得到总路径数。结果对1000000007取余以满足题目要求。
时间复杂度:
O(m*n)
空间复杂度:
O(m*n)
代码细节讲解
🦆
为什么在递归函数dfs中，每个单元格的初始计数设置为1？
▷🦆
在进行DFS时，如何保证不会重复访问同一个单元格，从而避免形成环路？
▷🦆
为什么在每次增加路径数量后要对1000000007取余？这里使用MOD的原因是什么？
▷🦆
当网格的尺寸非常大时，DFS的递归深度可能会如何影响算法的性能？是否有可能导致栈溢出？
▷