力扣10.10

329. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

数据范围

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 231 - 1

分析

对每个(i，j)点进行记忆化搜索，令dp[i][j]表示以(i，j)为结尾的最长路径，
遍历四个方向，状态转移如下

• $dp[i][j]=max(dp[i][j],dp[nx][ny]+1)$

代码

class Solution {
public:const static int N = 200 + 5;int n, m;int dp[N][N];bool vis[N][N];int dx[4] = {0, 1, 0, -1};int dy[4] = {1, 0, -1, 0};void dfs(int x, int y, vector<vector<int>>& matrix) {if(dp[x][y]) return ;for(int i = 0; i < 4; i ++ ) {int nx = x + dx[i];int ny = y + dy[i];if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;if(vis[nx][ny]) continue;if(matrix[nx][ny] >= matrix[x][y]) continue;vis[nx][ny] = true;dfs(nx, ny, matrix);dp[x][y] = max(dp[x][y], 1 + dp[nx][ny]); vis[nx][ny] = false;}return ;}int longestIncreasingPath(vector<vector<int>>& matrix) {n = matrix.size();m = matrix[0].size();int res = 0;for(int i = 0; i < n; i ++ ) {for(int j = 0; j < m; j ++ ) {dfs(i, j, matrix);res = max(res, dp[i][j]);}}return res + 1;}
};

---

2328. 网格图中递增路径的数目

给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。

请你返回在网格图中从 任意 格子出发，达到 任意 格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 109 + 7 取余 后返回。

如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。

数据范围

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 1000
• 1 <= m * n <= 105
• 1 <= grid[i][j] <= 105

分析

大致思路和上题差不多，令dp[i][j]为以(i,j)为终点的路径条数，初始化$dp[i][j]=1$，状态转移如下

• $dp[i][j]+=dp[nx][ny]$

代码

typedef long long LL;
class Solution {
public:const static int mod = 1e9 + 7, N = 1e3 + 5;int n, m;LL res = 0;LL dp[N][N];bool vis[N][N];int dx[4] = {0, 1, 0, -1};int dy[4] = {1, 0, -1, 0};int dfs(int x, int y, vector<vector<int>>& grid) {if(dp[x][y]) return dp[x][y];LL& t= dp[x][y];dp[x][y] = 1;for(int i = 0; i < 4; i ++ ) {int nx = x + dx[i];int ny = y + dy[i];if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;if(grid[nx][ny] >= grid[x][y]) continue;if(vis[nx][ny]) continue;vis[nx][ny] = true;t += dfs(nx, ny, grid);t %= mod;vis[nx][ny] = false;}return t;}LL countPaths(vector<vector<int>>& grid) {n = grid.size();m = grid[0].size();for(int i = 0; i < n; i ++ ) {for(int j = 0; j < m; j ++ ) {res += dfs(i, j, grid);;res %= mod;}}return res;}
};