矩阵最长递增路径

解题思路

对于矩阵中某一点，我们可以沿上下左右四个方向（边界情况除外）前进，在前进之后如果所在点的值小于等于上一点的值，那么说明此路径无效，返回上一点，并选取其他路径进行尝试。
因为每个点都有可能是路径的头，所以需要对矩阵中的所有点为头进行查找。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        int max = 0;
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                max = Math.max(max, dfs(matrix, i, j, -1));
            }
        }
        return max;
    }

    private int dfs (int[][] mat, int i, int j, int pre){
        if(mat[i][j] <= pre){
            return 0;
        }
        int max = 0;
        if(i > 0){
            max = Math.max(max, dfs(mat, i - 1, j, mat[i][j]));
        }
        if(j > 0){
            max = Math.max(max, dfs(mat, i, j - 1, mat[i][j]));
        }
        if(i < mat.length - 1){
            max = Math.max(max, dfs(mat, i + 1, j, mat[i][j]));
        }
        if(j < mat[i].length - 1){
            max = Math.max(max, dfs(mat, i, j + 1, mat[i][j]));
        }
        return max + 1;
    }
}

优化

如果我们已经知道以该点为头的最长递增路径长度，那么在dfs查找时可以直接使用这个长度，而无需再次计算，所以我们可以用一个矩阵将已经计算得到的最长递增路径chang

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    private int[][] maxMat;

    public int solve (int[][] matrix) {
        maxMat = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                maxMat[i][j] = 0;
            }
        }
        int max = 0;
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                max = Math.max(max, dfs(matrix, i, j, -1));
            }
        }
        return max;
    }

    private int dfs (int[][] mat, int i, int j, int pre){
        if(mat[i][j] <= pre){
            return 0;
        }
        if(maxMat[i][j] != 0){
            return maxMat[i][j];
        }
        int max = 0;
        if(i > 0){
            max = Math.max(max, dfs(mat, i - 1, j, mat[i][j]));
        }
        if(j > 0){
            max = Math.max(max, dfs(mat, i, j - 1, mat[i][j]));
        }
        if(i < mat.length - 1){
            max = Math.max(max, dfs(mat, i + 1, j, mat[i][j]));
        }
        if(j < mat[i].length - 1){
            max = Math.max(max, dfs(mat, i, j + 1, mat[i][j]));
        }
        maxMat[i][j] = max + 1;
        return max + 1;
    }
}