![Kimi LeetCode 2328.网站图中递增路径的数目 public int countPaths(int[][] grid)](http://pic.xiahunao.cn/yaotu/Kimi LeetCode 2328.网站图中递增路径的数目 public int countPaths(int[][] grid))
我来为你提供 LeetCode 2328「网格图中递增路径的数目」的 Java 实现。题目分析- n × m 网格每个格子有正整数- 从任意格子出发每次移动到严格大于当前值的相邻格子上下左右- 求所有递增路径的总数长度 ≥ 1 的路径即包含起点本身- 结果对 10^9 7 取模核心思路记忆化搜索 DFS1. 状态定义dp[i][j] 表示从格子 (i,j) 出发的递增路径数目2. 状态转移dp[i][j] 1 Σ dp[ni][nj]其中 (ni,nj) 是满足 grid[ni][nj] grid[i][j] 的相邻格子- 加 1 是因为路径只包含 (i,j) 本身也算一条路径3. 记忆化避免重复计算每个格子只计算一次4. 遍历所有起点最终答案为所有 dp[i][j] 之和Java 实现javaclass Solution {private static final int MOD 1_000_000_007;private static final int[][] DIRS {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};private int n, m;private int[][] grid;private int[][] memo; // memo[i][j] 表示从 (i,j) 出发的递增路径数public int countPaths(int[][] grid) {this.grid grid;this.n grid.length;this.m grid[0].length;this.memo new int[n][m];// 初始化 memo 为 -1表示未计算for (int i 0; i n; i) {for (int j 0; j m; j) {memo[i][j] -1;}}long ans 0;// 枚举所有起点for (int i 0; i n; i) {for (int j 0; j m; j) {ans (ans dfs(i, j)) % MOD;}}return (int) ans;}// 从 (i,j) 出发的递增路径数private int dfs(int i, int j) {// 已计算过直接返回if (memo[i][j] ! -1) {return memo[i][j];}// 路径只包含当前格子也算一条路径long count 1;// 遍历四个方向for (int[] dir : DIRS) {int ni i dir[0];int nj j dir[1];// 边界检查 严格递增检查if (ni 0 ni n nj 0 nj m grid[ni][nj] grid[i][j]) {count (count dfs(ni, nj)) % MOD;}}memo[i][j] (int) count;return memo[i][j];}}复杂度分析维度 复杂度 说明时间 O(nm) 每个格子只计算一次每次检查 4 个邻居空间 O(nm) memo 数组 递归栈深度最多 O(nm)关键点解释1. count 1 的含义每个格子自身构成长度为 1 的路径这是基础计数2. 严格递增grid[ni][nj] grid[i][j] 确保不会走回头路天然避免环3. 记忆化必要性没有记忆化会超时因为同一个格子可能被多次访问4. 取模时机每次加法都取模防止 int 溢出使用 long 做中间计算更安全5. 为什么不需要 visited 数组因为是严格递增不可能走回已访问的格子值只会越来越大所以不存在环
Kimi LeetCode 2328.网站图中递增路径的数目 public int countPaths(int[][] grid)
发布时间：2026/5/15 21:57:48
我来为你提供 LeetCode 2328「网格图中递增路径的数目」的 Java 实现。题目分析- n × m 网格每个格子有正整数- 从任意格子出发每次移动到严格大于当前值的相邻格子上下左右- 求所有递增路径的总数长度 ≥ 1 的路径即包含起点本身- 结果对 10^9 7 取模核心思路记忆化搜索 DFS1. 状态定义dp[i][j] 表示从格子 (i,j) 出发的递增路径数目2. 状态转移dp[i][j] 1 Σ dp[ni][nj]其中 (ni,nj) 是满足 grid[ni][nj] grid[i][j] 的相邻格子- 加 1 是因为路径只包含 (i,j) 本身也算一条路径3. 记忆化避免重复计算每个格子只计算一次4. 遍历所有起点最终答案为所有 dp[i][j] 之和Java 实现javaclass Solution {private static final int MOD 1_000_000_007;private static final int[][] DIRS {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};private int n, m;private int[][] grid;private int[][] memo; // memo[i][j] 表示从 (i,j) 出发的递增路径数public int countPaths(int[][] grid) {this.grid grid;this.n grid.length;this.m grid[0].length;this.memo new int[n][m];// 初始化 memo 为 -1表示未计算for (int i 0; i n; i) {for (int j 0; j m; j) {memo[i][j] -1;}}long ans 0;// 枚举所有起点for (int i 0; i n; i) {for (int j 0; j m; j) {ans (ans dfs(i, j)) % MOD;}}return (int) ans;}// 从 (i,j) 出发的递增路径数private int dfs(int i, int j) {// 已计算过直接返回if (memo[i][j] ! -1) {return memo[i][j];}// 路径只包含当前格子也算一条路径long count 1;// 遍历四个方向for (int[] dir : DIRS) {int ni i dir[0];int nj j dir[1];// 边界检查 严格递增检查if (ni 0 ni n nj 0 nj m grid[ni][nj] grid[i][j]) {count (count dfs(ni, nj)) % MOD;}}memo[i][j] (int) count;return memo[i][j];}}复杂度分析维度 复杂度 说明时间 O(nm) 每个格子只计算一次每次检查 4 个邻居空间 O(nm) memo 数组 递归栈深度最多 O(nm)关键点解释1. count 1 的含义每个格子自身构成长度为 1 的路径这是基础计数2. 严格递增grid[ni][nj] grid[i][j] 确保不会走回头路天然避免环3. 记忆化必要性没有记忆化会超时因为同一个格子可能被多次访问4. 取模时机每次加法都取模防止 int 溢出使用 long 做中间计算更安全5. 为什么不需要 visited 数组因为是严格递增不可能走回已访问的格子值只会越来越大所以不存在环
