我来为你提供 LeetCode 2328「网格图中递增路径的数目」的 Java 实现。

题目分析

- n × m 网格，每个格子有正整数
- 从任意格子出发，每次移动到严格大于当前值的相邻格子（上下左右）
- 求所有递增路径的总数（长度 ≥ 1 的路径，即包含起点本身）
- 结果对 `10^9 + 7` 取模

核心思路：记忆化搜索 + DFS

1. 状态定义：`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 实现

```java
class 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 数组：因为是严格递增，不可能走回已访问的格子（值只会越来越大），所以不存在环