题目描述链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/
解题思路：思路一：开始读完题后，首先想到的DFS+回溯进行解题，但由于此种做法会涉及多个节点的重复计算，导致超时，不能通过全部。先将其解题LeetCode代码放到下面以方便读者和下一思路代码比较：
class Solution { public: bool visited[1000][1000]; int dis[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int maxium; int longestIncreasingPath(vector<vector<int>>& matrix) { if(matrix.empty()){ return 0; } int M=matrix.size(); int N=matrix[0].size(); for(int i=0;i<M;i++){ for(int j=0;j<N;j++){ if(!visited[i][j]){ dfs(i,j,matrix,1); } } } return maxium; } void dfs(int x,int y,vector<vector<int>>& matrix,int length){ int M=matrix.size(); int N=matrix[0].size(); visited[x][y]=1; if(length>maxium){ maxium=length; } for(int i=0;i<4;i++){ int tx=x+dis[i][0]; int ty=y+dis[i][1]; if(tx<M&&ty<N&ty>=0&&tx>=0&&!visited[tx][ty]&&matrix[tx][ty]>matrix[x][y]){ dfs(tx,ty,matrix,length+1); } } visited[x][y]=0; } };
思路二：参考题解，采用记忆化搜索的方式进行搜索，就是以空间换取时间，将每次搜到的结果记忆下来，不再重复搜索，LeetCode解题代码如下（可以和思路一代码对比，查看不同之处）：
class Solution { public: bool visited[1000][1000]; int memo[1000][1000]; int dis[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int maxium; int longestIncreasingPath(vector<vector<int>>& matrix) { if(matrix.empty()){ return 0; } int M=matrix.size(); int N=matrix[0].size(); for(int i=0;i<M;i++){ for(int j=0;j<N;j++){ int l= dfs(i,j,matrix); if(l>maxium){ maxium=l; } } } return maxium; } int dfs(int x,int y,vector<vector<int>>& matrix){ int M=matrix.size(); int N=matrix[0].size(); if(memo[x][y]!=0){ return memo[x][y]; } memo[x][y]++; for(int i=0;i<4;i++){ int tx=x+dis[i][0]; int ty=y+dis[i][1]; if(tx<M&&ty<N&ty>=0&&tx>=0&&!visited[tx][ty]&&matrix[tx][ty]>matrix[x][y]){ int length=dfs(tx,ty,matrix); if(length+1>memo[x][y]){ memo[x][y]=length+1; } } } return memo[x][y]; } };
原文：https://www.cnblogs.com/zzw-/p/13382090.html