题解 | 矩阵最长递增路径

import java.util.*;


public class Solution {
    private static int result=0;
    private static int maxResult=0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        // write code here
           int[][] dp =new int[matrix.length][matrix[0].length];

           for(int r=0;r<matrix.length;r++){
            for(int j=0;j<matrix[0].length;j++){
                // dp 数组维护 以r j 为起点的最大的路径长度
                dfs(matrix,r,j,0,dp);
                // 当前路径长度
                dp[r][j]=result;
                maxResult=Math.max(result,maxResult);
                result=0;

            }
        }
        return maxResult;
    }
    // 我这个dfs 算法 是修改外部的路径 他的算法是没有问题的   但是可以拆解成分解子问题的形式 
     void dfs(int[][] grid, int i, int j,int path,int[][] dp){
        int m = grid.length, n = grid[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) {
            // 超出索引边界
            return;
        }




        // System.out.println("开始走方向");
        // // 开始走做
        // System.out.println(i);
        // System.out.println(j);
        // 进入当前节点 (i, j)
        path++;
        // 进入相邻节点（四叉树）
        // 上
        if( i-1>=0 &&  i-1<m && grid[i-1][j]>grid[i][j]){
            if(dp[i-1][j]!=0){
                result=Math.max(result,dp[i-1][j]+path);
               
            }else{
    dfs(grid, i - 1, j,path,dp);
            }
        
        }
        
        if( i+1>=0 && i+1<m && grid[i+1][j]>grid[i][j]){
            if(dp[i+1][j]!=0){
                result=Math.max(result,dp[i+1][j]+path);
             
            }else{
 dfs(grid, i + 1, j,path,dp);
            }
           
        }
        // 下
    
        // 左

        if( j-1>=0 && j-1<n && grid[i][j-1]>grid[i][j]){
            if(dp[i][j-1]!=0){
                result=Math.max(result,dp[i][j-1]+path);
            }else{
                 dfs(grid, i, j - 1,path,dp);
            }
           
        }
       
        if( j+1>=0 && j+1<n && grid[i][j+1]>grid[i][j]){
                if(dp[i][j+1]!=0){
                result=Math.max(result,dp[i][j+1]+path);
            }else{
                 dfs(grid, i, j + 1,path,dp);
            }
                 
        }
        // 右
        result=Math.max(result,path);
       
    }
}