以下是用 C++ 实现的 LeetCode 2328 题解，使用记忆化搜索（DFS + 记忆化）计算严格递增路径的数目：
class Solution {
int mod = 1e9 + 7;
vector<vector<int>> dp;
int m, n;
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int dfs(vector<vector<int>>& grid, int i, int j) {
if (dp[i][j] != 0) return dp[i][j];
long long count = 1; // 路径至少包含当前单元格
for (auto& dir : dirs) {
int ni = i + dir[0];
int nj = j + dir[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] > grid[i][j]) {
count = (count + dfs(grid, ni, nj)) % mod;
}
}
return dp[i][j] = count;
}
public:
int countPaths(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
dp.assign(m, vector<int>(n, 0));
long long ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
ans = (ans + dfs(grid, i, j)) % mod;
}
}
return ans;
}
};
算法思路：
问题理解：将矩阵视为有向无环图，每个单元格是一个节点，若相邻单元格的值严格大于当前单元格，则存在有向边。计算从任意单元格开始的所有严格递增路径数。
记忆化搜索：
-
定义 dp[i][j] 表示以 (i, j) 为起点的严格递增路径数目（包括自身）。
-
对于每个单元格，初始化路径数为 1（只包含自己），然后遍历四个方向，若相邻单元格值更大，则将其路径数累加到当前单元格。
-
使用递归计算并缓存结果，避免重复计算。
时间复杂度：O(m * n)，每个单元格计算一次。
空间复杂度：O(m * n)，用于存储 dp 数组。
关键点：
-
严格递增保证了图中无环，记忆化搜索不会陷入无限递归。
-
对 1e9+7 取模防止溢出。
-
通过遍历所有单元格并累加 dfs 结果得到总路径数。
