题解 | #61.矩阵最长递增路径#

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
}