Given an m x n integers matrix, return the length of the longest increasing path in matrix.
From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
Solution
很容易的一个做法就是枚举每个点，然后对每个点进行 \(DFS\). 但是会 \(TLE\).
考虑记忆化搜索，维护一个 \(dp\) 数组：
\[dp[x][y]=\max(dp[x][y], 1+dfs(nx,ny)) \]初始化 \(dp\) 我们用 \(-1\).
点击查看代码
class Solution {
private:
int dir[4][2]={
1,0,
0,1,
-1,0,
0,-1
};
bool check(int x, int y,int r, int c){
if(x<0||y<0||x>=r||y>=c) return false;
return true;
}
int ans=0;
int dfs(int x, int y, int r, int c, vector<vector<int>>& m, vector<vector<int>>&dp){
if(dp[x][y]!=-1)return dp[x][y];
dp[x][y]=1;
for(int i=0;i<4;i++){
int nx=x+dir[i][0], ny=y+dir[i][1];
if(check(nx,ny,r,c)&& m[nx][ny]>m[x][y]){
dp[x][y]=max(dp[x][y],1+dfs(nx,ny,r,c,m,dp));
}
}
return dp[x][y];
}
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int r = matrix.size(), c = matrix[0].size();
vector<vector<int>> dp(r, vector<int>(c,-1));
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
ans = max(ans, dfs(i,j,r,c,matrix,dp));
}
}
return ans;
}
};