题目描述
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 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]。注意不允许在对角线方向上移动。
解题思路：开始时想暴力的遍历矩阵，对每一个值DFS。提交后发现超时，最坏情况达到了o(n4)...于是增加了一个dp数组，相当于给递归加了缓存，用空间换时间。
int DFS(int x,int y,vector<vector<int>>& matrix,vector<vector<int>>& dp)
{
if(dp[x][y]!=0)
return dp[x][y];
int maxNum=1;
for(int i=-1;i<=1;++i)
for(int j=-1;j<=1;++j)
{
if((i+j==-1||i+j==1)&&x+i<matrix.size()&&x+i>=0&&y+j<matrix[0].size()&&y+j>=0)
{
if(matrix[x][y]<matrix[x+i][y+j])
{
int k=DFS(x+i,y+j,matrix,dp)+1;
maxNum=max(maxNum,k);
}
}
}
dp[x][y]=maxNum;
return maxNum;
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
int Max=0;
if(matrix.empty())
return 0;
vector<vector<int>> dp(matrix.size(),vector<int> (matrix[0].size()));
for(int i=0;i<matrix.size();++i)
for(int j=0;j<matrix[0].size();++j)
{
Max=max(DFS(i,j,matrix,dp),Max);
}
return Max;
}
