lc-329

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

示例 1：

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 
解释：最长递增路径为 [1, 2, 6, 9]。

示例 2：

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3：

输入：matrix = [[1]]
输出：1

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 231 - 1

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int[][] incrNum = new int[matrix.length][matrix[0].length];
        int longgest = 0;

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                int num = getIncrNum(matrix, incrNum, i, j);
                if (num > longgest) {
                    longgest = num;
                }
            }
        }
        return longgest;
    }

    private int getIncrNum(int[][] matrix, int[][] incrNum, int r, int c) {
        if (incrNum[r][c] > 0) {
            return incrNum[r][c];
        }

        int maxV = 1;
        if (r > 0 && matrix[r - 1][c] > matrix[r][c]) {
            int neighborV = getIncrNum(matrix, incrNum, r - 1, c) + 1;
            if (neighborV > maxV) {
                maxV = neighborV;
            }
        }
        if (r < matrix.length - 1 && matrix[r + 1][c] > matrix[r][c]) {
            int neighborV = getIncrNum(matrix, incrNum, r + 1, c) + 1;
            if (neighborV > maxV) {
                maxV = neighborV;
            }
        }
        if (c > 0 && matrix[r][c - 1] > matrix[r][c]) {
            int neighborV = getIncrNum(matrix, incrNum, r, c - 1) + 1;
            if (neighborV > maxV) {
                maxV = neighborV;
            }
        }
        if (c < matrix[0].length - 1 && matrix[r][c + 1] > matrix[r][c]) {
            int neighborV = getIncrNum(matrix, incrNum, r, c + 1) + 1;
            if (neighborV > maxV) {
                maxV = neighborV;
            }
        }
        incrNum[r][c] = maxV;
        return maxV;
    }
}
//leetcode submit region end(Prohibit modification and deletion)