给定一个整数矩阵，找出最长递增路径的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。示例 1:输入: nums = [ [9,9,4], [6,6,8], [2,1,1]] 输出: 4 解释: 最长递增路径为 [1, 2, 6, 9]。示例 2:输入: nums = [ [3,4,5], [3,2,6], [2,2,1]] 输出: 4 解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。算法：动态规划，设f[x][y]表示以x,y这个点为终点的最长递增路径，那么当x,y四个方向的下一个点能走时，
f[x][y]=max(f[x][y],f[a][b]+1)。但是当我们走到已经走过的点时，便没有必要枚举，这时可以开一个矩阵表示
点是否走过即可。(注意此题与最长上升子序列问题的区别)。另外这里递增是严格递增。
class Solution { public: vector<vector<int>>f; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; int dp(int x, int y, vector<vector<int>>& m){ if(f[x][y]!=-1)return f[x][y]; f[x][y]=1; for(int i=0;i<4;i++){ int a=x+dx[i],b=y+dy[i]; if(a>=0&&a<m.size()&&b>=0&&b<m[a].size()&&m[a][b]>m[x][y]) f[x][y]=max(f[x][y],dp(a,b,m)+1); } return f[x][y]; } int longestIncreasingPath(vector<vector<int>>& m) { int res=0; if(!m.size())return 0; f=vector<vector<int>>(m.size(),vector<int>(m[0].size(),-1)); for(int i=0;i<m.size();i++) for(int j=0;j<m[0].size();j++) res=max(res,dp(i,j,m)); return res; } };
转载于:https://www.cnblogs.com/programyang/p/11152629.html
