【Leetcode LCR 112】【记忆化搜索】矩阵中的最长递增路径

题目跳转这一道题十分有意思(bushi)我们来一起看一下1.题目考点与理解主要考点:记忆化搜索DFS 的递归思想与状态定义方向遍历与边界合法性判断主要理解:重要理解1: 不一定要从最小的1 11开始每一个都需要遍历(贪心思想错误)重要理解2暴力搜索会超时(随后验证),需要使用记忆化搜索2.错误案例与正确思路暴力搜索还是比较容易(实际不想浪费笔墨,bushi)的。不会可以看前面DFS的三讲(还是确实简单)classSolution{public:intdx[4]{-1,1,0,0};intdy[4]{0,0,-1,1};intans;// 暴力 DFS只传当前位置 当前长度voiddfs(intx,inty,intlen,vectorvectorintmat){// 每次进来都更新最大值ansmax(ans,len);for(intd0;d4;d){intnxxdx[d];intnyydy[d];if(nx0nxmat.size()ny0nymat[0].size()mat[nx][ny]mat[x][y]){// 往下搜长度 1dfs(nx,ny,len1,mat);// 这里没有存结果直接回来 —— 纯暴力}}}intlongestIncreasingPath(vectorvectorintmatrix){if(matrix.empty())return0;intmmatrix.size(),nmatrix[0].size();ans0;for(inti0;im;i){for(intj0;jn;j){// 每个点都从头暴力搜一遍dfs(i,j,1,matrix);}}returnans;}};正确思路:在枚举一个的起点( i , j ) (i,j)(i,j)时候可以进行路线到( a , b ) (a,b)(a,b),如果( a , b ) (a,b)(a,b)已经走过了再走一遍就浪费了(bushi),如果可以开一个二位数组d p [ i ] [ j ] dp[i][j]dp[i][j]表示从( i , j ) (i,j)(i,j)后的路线这样当走到( a , b ) (a,b)(a,b)时候就可以直接用d p [ a ] [ b ] dp[a][b]dp[a][b]然后再向回就可以了。十分无敌。这就是记忆化搜索3.分步详细解析代码模版:classSolution{public:intlongestIncreasingPath(vectorvectorintmatrix){}};首先先定义两端的长度d p dpdp数组classSolution{public:intm,n;vectorvectorintdp;intlongestIncreasingPath(vectorvectorintmatrix){mmatrix.size();nmatrix[0].size();dp.resize(m,vectorint(n,0));}};然后定义答案变量for每一个位置定义dfs函数classSolution{public:intm,n;vectorvectorintdp;intlongestIncreasingPath(vectorvectorintmatrix){mmatrix.size();nmatrix[0].size();dp.resize(m,vectorint(n,0));intans0;for(inti0;im;i){for(intj0;jn;j){ansmax(ans,dfs(i,j,matrix));}}}intdfs(inti,intj,vectorvectorintmat){}};定义方向数组判断记忆化classSolution{public:intm,n;vectorvectorintdp;intdx[4]{-1,1,0,0};intdy[4]{0,0,-1,1};intlongestIncreasingPath(vectorvectorintmatrix){mmatrix.size();nmatrix[0].size();dp.resize(m,vectorint(n,0));intans0;for(inti0;im;i){for(intj0;jn;j){ansmax(ans,dfs(i,j,matrix));}}}intdfs(inti,intj,vectorvectorintmat){if(dp[i][j])returndp[i][j];}};定义最长长度,向四方搜索判断合理性, 返回结果这里注意最大长度的状态转移是这样的最大长度 m a x ( 最大长度 , 1 d f s ( 新索引表格 ) ) 最大长度 max(最大长度, 1dfs(新索引表格))最大长度max(最大长度,1dfs(新索引表格))classSolution{public:intm,n;vectorvectorintdp;intdx[4]{-1,1,0,0};intdy[4]{0,0,-1,1};intlongestIncreasingPath(vectorvectorintmatrix){mmatrix.size();nmatrix[0].size();dp.resize(m,vectorint(n,0));intans0;for(inti0;im;i){for(intj0;jn;j){ansmax(ans,dfs(i,j,matrix));}}returnans;}intdfs(inti,intj,vectorvectorintmat){if(dp[i][j])returndp[i][j];intmaxlen1;for(intx0;x4;x){intnewiidx[x];intnewjjdy[x];if((newi0)(newim)(newj0)(newjn)(mat[newi][newj]mat[i][j])){maxlenmax(maxlen,1dfs(newi,newj,mat));}}dp[i][j]maxlen;returnmaxlen;}};谢谢大家点点赞了