赞
踩
给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。
对于每个单元格,你可以往上,下,左,右四个方向移动。
你 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。
数据范围:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1
因为只能从小的点走到大的点,所以是DAG,可以dp.
令d[i][j]表示从a[i][j]出发能走的最大路径,可以向四个方向转移.
int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; class Solution { public: int d[222][222]; int n,m; int dfs(vector<vector<int> >&a,int i,int j){ if(~d[i][j])return d[i][j]; d[i][j]=1; for(int k=0;k<4;k++){ int xx=i+dx[k]; int yy=j+dy[k]; if(xx<0||xx>=n||yy<0||yy>=m)continue; if(a[i][j]<a[xx][yy]){ d[i][j]=max(d[i][j],dfs(a,xx,yy)+1); } } return d[i][j]; } int longestIncreasingPath(vector<vector<int>>& a) { memset(d,-1,sizeof d); n=a.size(),m=a[0].size(); int ans=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ ans=max(ans,dfs(a,i,j)); } } return ans; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。