题解 | #61.矩阵最长递增路径#
矩阵最长递增路径
http://www.nowcoder.com/practice/7a71a88cdf294ce6bdf54c899be967a2
dfs递归
function solve( matrix ) {
let dirs = [ [0,1], //上
[0,-1], //下
[-1,0], //左
[1,0], //右
]; //四个方向
let m = matrix.length;
let n = matrix[0].length;
let dp = new Array(m+1);
for(let i=0; i<dp.length; i++)
dp[i] = new Array( n+1 ).fill(0);
function dfs(i,j){
if(dp[i][j]>0) return dp[i][j];
if(dp[i][j]==0) dp[i][j]=1;
for(let k=0; k<4; k++){
let nextI = i+dirs[k][0];
let nextJ = j+dirs[k][1];
if(nextI>=0 && nextI<m && nextJ>=0 && nextJ<n && matrix[nextI][nextJ]>matrix[i][j])
dp[i][j] = Math.max( dp[i][j],dfs(nextI,nextJ)+1 );
}
return dp[i][j];
}
if(m==0 || n==0) return 0;
let ans = 0;
for(let i=0; i<m; i++)
for(let j=0; j<n; j++)
ans = Math.max( ans, dfs(i,j) );
return ans
}
度是白月光
查看30道真题和解析
投递长鑫存储等公司8个岗位