深度优先搜索,思路不难,其中重要的是记忆化搜索,就是搜索的时候记录以当前节点为起点的最长路径的长度。贴代码
1 class Solution { 2 public: 3 int res = 0; 4 int m; 5 int n; 6 int longestIncreasingPath(vector<vector<int>>& matrix) 7 { 8 m = matrix.size(); 9 n = matrix[0].size(); 10 vector<vector<int>> memory(m,vector<int>(n,1)); 11 int res = 1; 12 for(int i = 0 ; i < m ; i++) 13 { 14 for(int j = 0 ; j < n ; j++) 15 { 16 if(memory[i][j] == 1) 17 { 18 int temp = dfs(matrix,i,j,memory); 19 if(temp>res) 20 res = temp; 21 } 22 } 23 } 24 return res; 25 } 26 int dfs(vector<vector<int>>& matrix,int i,int j,vector<vector<int>>& memory) 27 { 28 if(memory[i][j]!=1) 29 return memory[i][j]; 30 int max = 0; 31 int t1 = 0; 32 int t2 = 0; 33 int t3 = 0; 34 int t4 = 0; 35 if(i+1<m && matrix[i+1][j]>matrix[i][j]) 36 t1 = dfs(matrix,i+1,j,memory); 37 if(t1>max) 38 max = t1; 39 if(i-1>=0 && matrix[i-1][j]>matrix[i][j]) 40 t2 = dfs(matrix,i-1,j,memory); 41 if(t2>max) 42 max = t2; 43 if(j+1<n && matrix[i][j+1]>matrix[i][j]) 44 t3 = dfs(matrix,i,j+1,memory); 45 if(t3>max) 46 max = t3; 47 if(j-1>=0 && matrix[i][j-1]>matrix[i][j]) 48 t4 = dfs(matrix,i,j-1,memory); 49 if(t4>max) 50 max = t4; 51 memory[i][j] = max+1; 52 return max+1; 53 } 54 };