题目
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]] 输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]] 输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：
输入：matrix = [[1]] 输出：1
解题
方法一：记忆化dfs
正常思路下，遍历每个点，然后朝四个方向dfs，由于只会朝着递增的方向dfs，因此不用关注再次遍历已经访问过的点，但是这种方式会超时。
因此进行了记忆化，对于每个点，dp[i][j]表示，在位置i,j上为起点的最长递增路径
初始化dp[i][j]=1，因为每个点最短递增路径就是1，就是仅包含自身。
如果dp[i][j]不为1了，说明已经更新了该点，直接使用就行了。会出现还没更新完dp[i][j]，就去 访问该点的情况吗？是不会的，因为如果dp[i][j]还没更新完，那么也就是此时说在查找比matrix[i][j]更大的点，不可能访问matrix[i][j]。因此出现dp[i][j]不为1的情况，直接用就行了
class Solution { public: int m,n; vector<vector<int>> dirs={{-1,0},{0,-1},{1,0},{0,1}}; void dfs(vector<vector<int>>& matrix,vector<vector<int>>& dp,int x,int y){ for(vector<int>& dir:dirs){ int nx=x+dir[0]; int ny=y+dir[1]; if(nx<0||nx>=m||ny<0||ny>=n||matrix[nx][ny]<=matrix[x][y]) continue; if(dp[nx][ny]==1) dfs(matrix,dp,nx,ny); dp[x][y]=max(dp[x][y],dp[nx][ny]+1); } } int longestIncreasingPath(vector<vector<int>>& matrix) { m=matrix.size(),n=matrix[0].size(); vector<vector<int>> dp(m,vector<int>(n,1)); int res=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(dp[i][j]!=1) continue; dfs(matrix,dp,i,j); res=max(res,dp[i][j]); } } return res; } };
方法二：拓扑排序
将矩阵转化成一张拓扑图
进行多源的拓扑排序
拓扑排序的深度，就是最长的递增路径
class Solution { public: int m,n; vector<vector<int>> dirs={{-1,0},{0,-1},{1,0},{0,1}}; int longestIncreasingPath(vector<vector<int>>& matrix) { m=matrix.size(),n=matrix[0].size(); //计算入度 vector<vector<int>> indeg(m,vector<int>(n,0)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ for(vector<int>& dir:dirs){ int nx=i+dir[0],ny=j+dir[1]; if(nx<0||nx>=m||ny<0||ny>=n||matrix[nx][ny]<=matrix[i][j]) continue; indeg[nx][ny]++; } } } //拓扑排序 queue<pair<int,int>> q; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(indeg[i][j]==0){ q.push({i,j}); } } } int res=0; while(!q.empty()){ res++; int l=q.size(); while(l--){ auto [x,y]=q.front(); q.pop(); for(vector<int>& dir:dirs){ int nx=x+dir[0],ny=y+dir[1]; if(nx<0||nx>=m||ny<0||ny>=n||matrix[nx][ny]<=matrix[x][y]) continue;//这样子就可以不用浪费额外空间建图 if(--indeg[nx][ny]==0) q.push({nx,ny}); } } } return res; } };
