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

import java.util.*;

/**
 * NC138 矩阵最长递增路径
 * @author d3y1
 */
public class Solution {
    private int ROW;
    private int COL;
    private int[] dx = new int[]{0, 1, 0, -1};
    private int[] dy = new int[]{1, 0, -1, 0};

    private int result = 0;
    private int[][] dp;

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

    /**
     * 模拟法: 递归 && 动态规划
     * @param matrix
     * @return
     */
    private int solution(int[][] matrix){
        ROW = matrix.length;
        COL = matrix[0].length;

        dp = new int[ROW][COL];

        for(int i=0; i<ROW; i++){
            for(int j=0; j<COL; j++){
                result = Math.max(result, dfs(matrix, i, j));
            }
        }

        return result;
    }

    /**
     * dfs
     * @param matrix
     * @param x
     * @param y
     */
    private int dfs(int[][] matrix, int x, int y){
        if(dp[x][y] > 0){
            return dp[x][y];
        }

        dp[x][y]++;

        for(int i=0; i<4; i++){
            int nextX = x+dx[i];
            int nextY = y+dy[i];
            if(isValid(nextX, nextY) && matrix[x][y]<matrix[nextX][nextY]){
                dp[x][y] = Math.max(dp[x][y], dfs(matrix, nextX, nextY)+1);
            }
        }

        return dp[x][y];
    }

    /**
     * 是否合法(是否越界)
     * @param x
     * @param y
     * @return
     */
    private boolean isValid(int x, int y){
        if(x<0 || x>=ROW || y<0 || y>=COL){
            return false;
        }

        return true;
    }
}