企业官网建设流程全解析

以下是用 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; } };

算法思路：

1. 问题理解：将矩阵视为有向无环图，每个单元格是一个节点，若相邻单元格的值严格大于当前单元格，则存在有向边。计算从任意单元格开始的所有严格递增路径数。

2. 记忆化搜索：

   • 定义dp[i][j]表示以(i, j)为起点的严格递增路径数目（包括自身）。

   • 对于每个单元格，初始化路径数为 1（只包含自己），然后遍历四个方向，若相邻单元格值更大，则将其路径数累加到当前单元格。

   • 使用递归计算并缓存结果，避免重复计算。

3. 时间复杂度：O(m * n)，每个单元格计算一次。

4. 空间复杂度：O(m * n)，用于存储dp数组。

关键点：

• 严格递增保证了图中无环，记忆化搜索不会陷入无限递归。

• 对 1e9+7 取模防止溢出。

• 通过遍历所有单元格并累加dfs结果得到总路径数。