给定一个矩阵，矩阵内所有数均为非负整数。
求一条路径，该路径上所有数是递增的。
这个路径必须满足以下条件：
1、对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。
2、你不能走重复的单元格。即每个格子最多只能走一次。
示例1
复制
[[1,2,3],[4,5,6],[7,8,9]]复制
5
思路：
经典的海拔问题，对于二维矩阵的每一个值
若它比周围的值都小，那么只能单独一个组成递增序列，此时dp[x][y]=1;否则，dp[x][y]的值 取四方向 dp最大值+1 即与当前(x,y)组成一个更长的递增序列。实现细节：
初始化dp[][]为0表示 未被赋值，i从0=>height j从0=>width dfs(x,y)返回(x,y)为终点的最长递增序列长度。
采取备忘录方法，若dp[x][y]!=0 直接返回，否则进入四方向计算，返回前 填写备忘录
为什么无法使用动态规划？
动态规划通常是一行一行的迭代计算，而在本问题中，一个位置计算需要使用其四方向位置值。
不满足分解成小规模问题的要求。
另外注意一点，本问题与搜索问题不同，搜索问题通常采取visit数组标记已经访问过的避免重复dfs
但本问题不需要visit标记，因为dfs过程中，总是进入比当前(x,y)值更小的方向，不会反向dfs回来。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 递增路径的最大长度 * @param matrix int整型vector<vector<>> 描述矩阵的每个数 * @return int整型 */ int width,height; int high[1001][1001];//存放每个节点的累积高度 //初始化为0 high[x][y]表示以(x,y)为终点递增序列长度 int dfs(int x,int y,vector<vector<int>> & map) //返回以(x,y)为终点的递增路径长度 { if(high[x][y]!=0) //已经填充过值了 return high[x][y]; int h=1;//仅仅自己一个节点 //注意这里 不会出现dfs相互双向无限推诿情况 （因为dfs只会进入 值更小的内层） //即 dfs最后递归返回点 是比四周都小的点 if(x-1>0 && map[x-1][y]<map[x][y] ) //若果左边节点比当前小 h=max(h,dfs(x-1,y,map)+1); if(y-1>0 && map[x][y-1]<map[x][y] ) //若果下边节点比当前小 h=max(h,dfs(x,y-1,map)+1); if(x+1<width && map[x+1][y]<map[x][y] ) //若果左边节点比当前小 h=max(h,dfs(x+1,y,map)+1); if(y+1<height && map[x][y+1]<map[x][y] ) //若果左边节点比当前小 h=max(h,dfs(x,y+1,map)+1); high[x][y]=h;//备忘录保存 return h; } int solve(vector<vector<int> >& matrix) { // write code here int ans=0; height=matrix.size(); width=matrix[0].size(); for(int i=0;i<height;i++) for(int j=0;j<width;j++) { ans=max(ans,dfs(i,j,matrix)); } return ans; } };
