题解 | 矩阵最长递增路径

import java.util.*;

public class Solution {
    private int ans = 0;

    public int solve(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        int row = matrix.length;
        int col = matrix[0].length;

        int[][] memo = new int[row][col];

        for (int i = 0; i <row; i++) {
            for (int j = 0; j <col; j++) {
                dfs(matrix, i, j, 0, memo);
            }
        }
        return ans;
    }

    private int dfs(int[][] matrix, int i, int j, int length, int[][] memo) {
        if (memo[i][j] != 0) {
            ans = Math.max(ans, length + memo[i][j]);
            return memo[i][j];
        }

        int maxPathFromHere = 1;

        if (i >= 1 && matrix[i - 1][j] > matrix[i][j])
            maxPathFromHere = Math.max(maxPathFromHere, dfs(matrix, i - 1, j, 0, memo) + 1);
        if (i < matrix.length - 1 && matrix[i + 1][j] > matrix[i][j])
            maxPathFromHere = Math.max(maxPathFromHere, dfs(matrix, i + 1, j, 0, memo) + 1);
        if (j >= 1 && matrix[i][j - 1] > matrix[i][j])
            maxPathFromHere = Math.max(maxPathFromHere, dfs(matrix, i, j - 1, 0, memo) + 1);
        if (j < matrix[0].length - 1 && matrix[i][j + 1] > matrix[i][j])
            maxPathFromHere = Math.max(maxPathFromHere, dfs(matrix, i, j + 1, 0, memo) + 1);

        memo[i][j] = maxPathFromHere;

        ans = Math.max(ans, length + maxPathFromHere);

        return maxPathFromHere;
    }
}