题解 | #矩阵最长递增路径，记忆化递归#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0 ;
        int rl = matrix.length ;
        int cl = matrix[0].length ;
        int res = 0 ;
        int[][] dp = new int[rl][cl] ;//dp[i][j]表示map[i][j]开头的最长递增路径的长度
        for(int i = 0 ; i < rl ; i ++) {
            for(int j = 0 ; j < cl ; j ++) {
                res = Math.max(res , dfs(matrix , dp , i , j)) ;
            }
        }
        return res ;
    }
    //记忆化递归，dp[i][j]表示map[i][j]开头的最长递增路径的长度
    //本函数的功能：找到以map[i][j]开头的最长递增路径的长度
    public int dfs(int map[][] , int[][] dp , int i , int j) {
        if(dp[i][j] != 0) return dp[i][j] ;
        dp[i][j] ++ ;
        int[][] deviation = {{-1 , 0} , {1 , 0} , {0 , -1} , {0 , 1}} ;//偏移：四个方向
        for(int x = 0 ; x < 4 ; x ++) {//枚举i,j四周的点
            int next_i = i + deviation[x][0] ;
            int next_j = j + deviation[x][1] ;
            //坐标合法且递增
            if(next_i >= 0 && next_i < map.length && next_j >= 0 && next_j < map[0].length && map[next_i][next_j] > map[i][j]) {
                dp[i][j] = Math.max(dp[i][j] , dfs(map , dp , next_i , next_j) + 1) ;//更新dp[i]
            }
        }
        return dp[i][j] ;
    }
}