Given an /(m /times 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
我们需要从每个cell来进行搜索：对于每一个位置，我们用 /(dfs(i,j)/) 来返回位置 /((i,j)/) 为起点的最长递增序列长度，考虑转移，如果相邻位置的 /((ni,nj)/) 满足 /(m[ni][nj]>m[i][j]/):
/[dp[i][j] = /max(dp[i][j],dfs(ni,nj)+1)
/]
最后用 /(dp[i][j]/) 来返回 /(dfs(i,j)/)
点击查看代码
class Solution {
private:
int dp[202][202];
int ans = -1;
int dir[4][2]={1,0, 0,1, 0,-1, -1,0};
int check(int x, int y, int r, int c){
if(x<0||x>=r||y<0||y>=c)return 0;
return 1;
}
int dfs(int x, int y, int r, int c, vector<vector<int>>& m){
if(dp[x][y])return dp[x][y];
for(int i=0;i<4;i++){
int nx = x+dir[i][0];
int ny = y+dir[i][1];
if(check(nx,ny,r,c)){
if(m[nx][ny]>m[x][y])
dp[x][y] = max(dp[x][y],1+dfs(nx,ny,r,c,m));
}
}
return dp[x][y];
}
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int r = matrix.size();
int c = matrix[0].size();
if(r==1&&c==1) return matrix[0][0];
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
ans = max(ans,dfs(i,j,r,c,matrix));
return ans+1;
}
};
原创文章，作者：745907710，如若转载，请注明出处：https://blog.ytso.com/274486.html